Submission #1871014
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,b,a) for(int i = (b) - 1; i >= (a); i--)
#define ITER(it, a) for(typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a, value) memset(a, value, sizeof(a))
#define SZ(a) (int) a.size()
#define ALL(a) a.begin(),a.end()
#define PB push_back
#define MP make_pair
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
const double PI = acos(-1.0);
const LL INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL)INF;
const int MAX = 100100;
struct RMQ
{
int A[MAX * 4];
int P[MAX * 4];
int n;
void init(int n)
{
this->n = n;
FOR (i, 0, n*4)
{
A[i] = -1;
P[i] = -1;
}
}
void upd(int v, int val)
{
A[v] = val;
P[v] = val;
}
void push(int v, int tl, int tr)
{
if (tl == tr || P[v] == -1) return;
upd(v*2, P[v]);
upd(v*2+1, P[v]);
P[v] = -1;
}
void upd(int tl, int tr, int v, int l, int r, int val)
{
if (l > r) return;
push(v, tl, tr);
if (l == tl && r == tr)
{
upd(v, val);
return;
}
int tm = (tl + tr) / 2;
upd(tl, tm, v*2, l, min(tm, r), val);
upd(tm+1, tr, v*2+1, max(tm+1, l), r, val);
}
void paint(int l, int r, int c)
{
upd(0, n-1, 1, l, r, c);
}
int get(int tl, int tr, int v, int x)
{
push(v, tl, tr);
if (tl == tr)
{
return A[v];
}
int tm = (tl + tr) / 2;
if (x <= tm) return get(tl, tm, v*2, x);
return get(tm+1, tr, v*2+1, x);
}
int get(int x)
{
return get(0, n-1, 1, x);
}
} R;
struct Fen
{
int A[MAX];
int n;
void init(int n)
{
this->n = n;
}
void add(int x, int val)
{
for (; x < n; x = x | (x + 1))
{
A[x] += val;
}
}
void add(int l, int r, int val)
{
add(l, val);
add(r+1, -val);
}
int get(int x)
{
int res = 0;
for (; x >= 0; x = (x & (x + 1)) - 1)
{
res += A[x];
}
return res;
}
} F;
int A[MAX];
int B[MAX];
vector<PII> C;
VI v;
int getInd(int x)
{
return lower_bound(ALL(v), x) - v.begin();
}
LL DP[MAX][2];
int len(int x, int y, int mod)
{
if (y >= x) return y - x;
return y - x + mod;
}
int main()
{
//freopen("in.txt", "r", stdin);
//ios::sync_with_stdio(false); cin.tie(0);
int n, k;
scanf("%d%d", &n, &k);
LL add = 0;
FOR (i, 0, n)
{
scanf("%d%d", &A[i], &B[i]);
add += A[i];
}
int sum = 0;
FOR (i, 0, n)
{
int ns = sum + A[i];
ns %= k;
if (B[i] == 1)
{
if (2 * A[i] >k)
{
cout<<-1<<endl;
return 0;
}
C.PB(MP(-2*sum, -2*ns));
}
sum = ns;
}
FOR (i, 0, SZ(C))
{
C[i].first %= k;
if (C[i].first < 0) C[i].first += k;
C[i].second %= k;
if (C[i].second < 0) C[i].second += k;
v.PB(C[i].first);
v.PB(C[i].second);
}
sort(ALL(v));
v.erase(unique(ALL(v)), v.end());
R.init(SZ(v));
/*FOR (i, 0, SZ(C))
{
cout<<C[i].first<<' '<<C[i].second<<endl;
}*/
RFOR(i, SZ(C), 0)
{
int x = C[i].first;
int c = R.get(getInd(x));
if (c == -1) DP[i][0] = 0;
else
{
DP[i][0] = DP[c][0] + len(x, C[c].first, k);
}
x = C[i].second;
c = R.get(getInd(x));
if (c == -1) DP[i][1] = 0;
else
{
DP[i][1] = DP[c][0] + len(x, C[c].first, k);
}
int l = getInd(C[i].first);
int r = getInd(C[i].second);
if (l > r)
{
R.paint(r+1, l-1, i);
}
else
{
R.paint(0, l-1, i);
R.paint(r+1, SZ(v)-1, i);
}
}
F.init(SZ(v));
LL res = LINF;
FOR (i, 0, SZ(C))
{
int x = C[i].first;
int cnt = F.get(getInd(x));
if (cnt == i) res = min(res, DP[i][0]);
x = C[i].second;
cnt = F.get(getInd(x));
if (cnt == i) res = min(res, DP[i][1]);
int l = getInd(C[i].first);
int r = getInd(C[i].second);
if (l <= r)
{
F.add(l, r, 1);
}
else
{
F.add(0, r, 1);
F.add(l, SZ(v)-1, 1);
}
}
res += add * 2;
cout<<res<<endl;
}
Submission Info
Submission Time |
|
Task |
F - Train Service Planning |
User |
vjudge4 |
Language |
C++14 (GCC 5.4.1) |
Score |
1700 |
Code Size |
3780 Byte |
Status |
AC |
Exec Time |
178 ms |
Memory |
7796 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:156:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &k);
^
./Main.cpp:160:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &A[i], &B[i]);
^
Judge Result
Set Name |
Sample |
All |
subtask |
subtask2 |
Score / Max Score |
0 / 0 |
700 / 700 |
500 / 500 |
500 / 500 |
Status |
|
|
|
|
Set Name |
Test Cases |
Sample |
sample1.txt, sample2.txt, sample3.txt, sample4.txt |
All |
sample1.txt, sample2.txt, sample3.txt, sample4.txt, in1.txt, in10.txt, in101.txt, in102.txt, in103.txt, in104.txt, in105.txt, in106.txt, in107.txt, in108.txt, in109.txt, in11.txt, in110.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in3.txt, in4.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt, sample3.txt, sample4.txt, sub2in1.txt, sub2in10.txt, sub2in11.txt, sub2in12.txt, sub2in13.txt, sub2in14.txt, sub2in15.txt, sub2in16.txt, sub2in17.txt, sub2in18.txt, sub2in19.txt, sub2in2.txt, sub2in20.txt, sub2in21.txt, sub2in22.txt, sub2in23.txt, sub2in24.txt, sub2in3.txt, sub2in4.txt, sub2in5.txt, sub2in6.txt, sub2in7.txt, sub2in8.txt, sub2in9.txt, subin1.txt, subin10.txt, subin101.txt, subin102.txt, subin103.txt, subin104.txt, subin105.txt, subin106.txt, subin107.txt, subin108.txt, subin109.txt, subin11.txt, subin12.txt, subin13.txt, subin14.txt, subin15.txt, subin16.txt, subin17.txt, subin18.txt, subin19.txt, subin2.txt, subin20.txt, subin201.txt, subin21.txt, subin22.txt, subin23.txt, subin24.txt, subin3.txt, subin4.txt, subin5.txt, subin6.txt, subin7.txt, subin8.txt, subin9.txt |
subtask |
sample1.txt, sample2.txt, sample3.txt, subin1.txt, subin10.txt, subin101.txt, subin102.txt, subin103.txt, subin104.txt, subin105.txt, subin106.txt, subin107.txt, subin108.txt, subin109.txt, subin11.txt, subin12.txt, subin13.txt, subin14.txt, subin15.txt, subin16.txt, subin17.txt, subin18.txt, subin19.txt, subin2.txt, subin20.txt, subin201.txt, subin21.txt, subin22.txt, subin23.txt, subin24.txt, subin3.txt, subin4.txt, subin5.txt, subin6.txt, subin7.txt, subin8.txt, subin9.txt |
subtask2 |
sample1.txt, sample2.txt, sample3.txt, sample4.txt, sub2in1.txt, sub2in10.txt, sub2in11.txt, sub2in12.txt, sub2in13.txt, sub2in14.txt, sub2in15.txt, sub2in16.txt, sub2in17.txt, sub2in18.txt, sub2in19.txt, sub2in2.txt, sub2in20.txt, sub2in21.txt, sub2in22.txt, sub2in23.txt, sub2in24.txt, sub2in3.txt, sub2in4.txt, sub2in5.txt, sub2in6.txt, sub2in7.txt, sub2in8.txt, sub2in9.txt |
Case Name |
Status |
Exec Time |
Memory |
in1.txt |
AC |
2 ms |
2304 KB |
in10.txt |
AC |
98 ms |
5496 KB |
in101.txt |
AC |
66 ms |
5112 KB |
in102.txt |
AC |
63 ms |
5496 KB |
in103.txt |
AC |
69 ms |
4728 KB |
in104.txt |
AC |
60 ms |
5880 KB |
in105.txt |
AC |
59 ms |
6136 KB |
in106.txt |
AC |
67 ms |
5112 KB |
in107.txt |
AC |
63 ms |
5496 KB |
in108.txt |
AC |
69 ms |
4728 KB |
in109.txt |
AC |
60 ms |
5880 KB |
in11.txt |
AC |
98 ms |
5624 KB |
in110.txt |
AC |
59 ms |
6136 KB |
in12.txt |
AC |
96 ms |
5624 KB |
in13.txt |
AC |
94 ms |
5496 KB |
in14.txt |
AC |
96 ms |
5624 KB |
in15.txt |
AC |
91 ms |
5624 KB |
in16.txt |
AC |
93 ms |
5624 KB |
in17.txt |
AC |
94 ms |
5624 KB |
in18.txt |
AC |
95 ms |
5624 KB |
in19.txt |
AC |
93 ms |
5624 KB |
in2.txt |
AC |
99 ms |
5624 KB |
in20.txt |
AC |
94 ms |
5624 KB |
in21.txt |
AC |
74 ms |
5624 KB |
in22.txt |
AC |
70 ms |
5624 KB |
in23.txt |
AC |
77 ms |
5624 KB |
in24.txt |
AC |
78 ms |
5624 KB |
in25.txt |
AC |
28 ms |
4472 KB |
in26.txt |
AC |
28 ms |
4472 KB |
in27.txt |
AC |
27 ms |
4472 KB |
in28.txt |
AC |
30 ms |
4472 KB |
in3.txt |
AC |
97 ms |
5496 KB |
in4.txt |
AC |
99 ms |
5624 KB |
in5.txt |
AC |
84 ms |
5240 KB |
in6.txt |
AC |
93 ms |
5624 KB |
in7.txt |
AC |
92 ms |
4984 KB |
in8.txt |
AC |
18 ms |
3072 KB |
in9.txt |
AC |
98 ms |
5624 KB |
sample1.txt |
AC |
1 ms |
2304 KB |
sample2.txt |
AC |
1 ms |
256 KB |
sample3.txt |
AC |
1 ms |
2304 KB |
sample4.txt |
AC |
1 ms |
2304 KB |
sub2in1.txt |
AC |
2 ms |
2304 KB |
sub2in10.txt |
AC |
2 ms |
2304 KB |
sub2in11.txt |
AC |
2 ms |
2304 KB |
sub2in12.txt |
AC |
2 ms |
2304 KB |
sub2in13.txt |
AC |
2 ms |
2304 KB |
sub2in14.txt |
AC |
2 ms |
2304 KB |
sub2in15.txt |
AC |
2 ms |
2304 KB |
sub2in16.txt |
AC |
2 ms |
2304 KB |
sub2in17.txt |
AC |
2 ms |
2304 KB |
sub2in18.txt |
AC |
1 ms |
2304 KB |
sub2in19.txt |
AC |
2 ms |
2304 KB |
sub2in2.txt |
AC |
2 ms |
2304 KB |
sub2in20.txt |
AC |
2 ms |
2304 KB |
sub2in21.txt |
AC |
2 ms |
2304 KB |
sub2in22.txt |
AC |
2 ms |
2304 KB |
sub2in23.txt |
AC |
2 ms |
2304 KB |
sub2in24.txt |
AC |
2 ms |
2304 KB |
sub2in3.txt |
AC |
2 ms |
2304 KB |
sub2in4.txt |
AC |
1 ms |
2304 KB |
sub2in5.txt |
AC |
2 ms |
2304 KB |
sub2in6.txt |
AC |
2 ms |
2304 KB |
sub2in7.txt |
AC |
1 ms |
256 KB |
sub2in8.txt |
AC |
2 ms |
2304 KB |
sub2in9.txt |
AC |
2 ms |
2304 KB |
subin1.txt |
AC |
177 ms |
7796 KB |
subin10.txt |
AC |
172 ms |
7796 KB |
subin101.txt |
AC |
119 ms |
7796 KB |
subin102.txt |
AC |
99 ms |
7796 KB |
subin103.txt |
AC |
95 ms |
7796 KB |
subin104.txt |
AC |
93 ms |
7796 KB |
subin105.txt |
AC |
82 ms |
7796 KB |
subin106.txt |
AC |
81 ms |
7796 KB |
subin107.txt |
AC |
99 ms |
7796 KB |
subin108.txt |
AC |
108 ms |
7796 KB |
subin109.txt |
AC |
98 ms |
7796 KB |
subin11.txt |
AC |
162 ms |
7796 KB |
subin12.txt |
AC |
167 ms |
7796 KB |
subin13.txt |
AC |
169 ms |
7796 KB |
subin14.txt |
AC |
171 ms |
7796 KB |
subin15.txt |
AC |
169 ms |
7796 KB |
subin16.txt |
AC |
170 ms |
7796 KB |
subin17.txt |
AC |
159 ms |
7540 KB |
subin18.txt |
AC |
164 ms |
7540 KB |
subin19.txt |
AC |
166 ms |
7540 KB |
subin2.txt |
AC |
174 ms |
7540 KB |
subin20.txt |
AC |
168 ms |
7540 KB |
subin201.txt |
AC |
1 ms |
2304 KB |
subin21.txt |
AC |
37 ms |
6004 KB |
subin22.txt |
AC |
37 ms |
6004 KB |
subin23.txt |
AC |
39 ms |
6004 KB |
subin24.txt |
AC |
39 ms |
6004 KB |
subin3.txt |
AC |
178 ms |
7796 KB |
subin4.txt |
AC |
150 ms |
6900 KB |
subin5.txt |
AC |
166 ms |
7796 KB |
subin6.txt |
AC |
114 ms |
7796 KB |
subin7.txt |
AC |
19 ms |
3960 KB |
subin8.txt |
AC |
17 ms |
3960 KB |
subin9.txt |
AC |
177 ms |
7796 KB |