Submission #1693746
Source Code Expand
#include <iostream>
#include <cstdio>
#include <map>
#include <algorithm>
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define dep(i,a,b) for(int i = a; i >= b; i--)
using namespace std;
typedef long long LL;
const LL inf = 1LL << 60;
const int N = 1e6 + 10;
int n, k, a[N], b[N], nd[N], t = 0;
map<int, int> val;
void init() {
int delta = 0;
t = 2; nd[1] = 1, nd[2] = k;
rep(i,1,n) {
if (b[i] == 1) {
int l = 1, r = 2 * a[i] - 1;
l = (l - delta + k) % k, r = (r - delta + k) % k;
int r1 = (r + 1) % k, l1 = (l - 1 + k) % k;
if (l == 0) l = k; if (r == 0) r = k;
if (r1 == 0) r1 = k; if (l1 == 0) l1 = k;
nd[++t] = l, nd[++t] = r, nd[++t] = r1, nd[++t] = l1, nd[++t] = k - delta;
}
delta = ((delta - 2LL * a[i]) % k + k) % k;
}
sort(nd + 1, nd + t + 1); t = unique(nd + 1, nd + t + 1) - nd - 1;
rep(i,1,t) val[nd[i]] = i;
}
LL ans = 0;
namespace seg{
int a, b; LL s[N << 2], c; bool tag[N << 2];
#define lc (x << 1)
#define rc (lc | 1)
#define mid ((l + r) >> 1)
#define lcq lc, l, mid
#define rcq rc, mid + 1, r
void build(int x, int l, int r) {
s[x] = nd[l]; tag[x] = false;
if (l < r) build(lcq), build(rcq);
}
inline void push(int x, int l, int r) {
if (tag[x]) {
s[x] = inf; if (l < r) tag[lc] = tag[rc] = true;
tag[x] = false;
}
}
LL qry(int x, int l, int r) {
push(x, l, r);
if (a <= l && r <= b) return s[x];
else {
LL ans = inf;
if (a <= mid) ans = min(ans, qry(lcq));
if (b > mid) ans = min(ans, qry(rcq));
return ans;
}
}
void upd(int x) { s[x] = min(s[lc], s[rc]); }
void clear(int x, int l, int r) {
if (a <= l && r <= b) tag[x] = true, push(x, l, r);
else {
push(x, l, r);
if (a <= mid) clear(lcq); else push(lcq);
if (b > mid) clear(rcq); else push(rcq);
upd(x);
}
}
void upd(int x, int l, int r) {
push(x, l, r);
if (l == r) s[x] = min(s[x], c);
else (a <= mid ? upd(lcq), push(rcq) : upd(rcq), push(lcq)), upd(x);
}
void calc(int x, int l, int r) {
push(x, l, r);
if (l == r) ans = min(ans, s[x] - nd[l]);
else calc(lcq), calc(rcq);
}
}
int delta = 0;
LL ask(int l, int r) {
int d = val[k - delta]; LL ans = inf;
if (l <= d && d < r) {
seg::a = l, seg::b = d; ans = seg::qry(1, 1, t) + delta;
seg::a = d + 1, seg::b = r; ans = min(ans, seg::qry(1, 1, t) + delta - k);
} else {
seg::a = l, seg::b = r; ans = seg::qry(1, 1, t) + delta;
if (d < l) ans -= k;
}
seg::a = l, seg::b = r, seg::clear(1, 1, t);
return ans;
}
void work() {
seg::build(1, 1, t);
rep(i,1,n) {
if (b[i] == 1) {
int l = 1, r = 2 * a[i] - 1;
l = (l - delta + k) % k, r = (r - delta + k) % k;
if (l == 0) l = k; if (r == 0) r = k;
LL mn = inf;
if (l <= r) mn = ask(val[l], val[r]);
else mn = min(ask(val[l], t), ask(1, val[r]));
seg::a = val[k - delta], seg::c = mn + k - delta;
seg::upd(1, 1, t);
}
delta = ((delta - 2LL * a[i]) % k + k) % k;
}
}
int main() {
scanf("%d%d",&n,&k);
rep(i,1,n) {
scanf("%d%d",a + i, b + i);
if (a[i] * 2 > k && b[i] == 1) { printf("-1\n"); return 0; }
}
init();
work();
LL sum = 0; rep(i,1,n) sum += a[i];
ans = inf;
seg::calc(1, 1, t);
printf("%lld\n",ans + sum * 2);
return 0;
}
Submission Info
Submission Time
2017-10-19 20:24:41+0900
Task
F - Train Service Planning
User
WuHongxun
Language
C++14 (GCC 5.4.1)
Score
1700
Code Size
3321 Byte
Status
AC
Exec Time
423 ms
Memory
35840 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:122:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&k);
^
./Main.cpp:124:29: 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
5 ms
8576 KB
in10.txt
AC
210 ms
22656 KB
in101.txt
AC
112 ms
16640 KB
in102.txt
AC
128 ms
18944 KB
in103.txt
AC
102 ms
14464 KB
in104.txt
AC
141 ms
23296 KB
in105.txt
AC
142 ms
24192 KB
in106.txt
AC
110 ms
16640 KB
in107.txt
AC
124 ms
18944 KB
in108.txt
AC
99 ms
14464 KB
in109.txt
AC
147 ms
23424 KB
in11.txt
AC
215 ms
23296 KB
in110.txt
AC
139 ms
24192 KB
in12.txt
AC
203 ms
23296 KB
in13.txt
AC
199 ms
22528 KB
in14.txt
AC
207 ms
23296 KB
in15.txt
AC
196 ms
23296 KB
in16.txt
AC
201 ms
23296 KB
in17.txt
AC
202 ms
23296 KB
in18.txt
AC
210 ms
23296 KB
in19.txt
AC
203 ms
23168 KB
in2.txt
AC
215 ms
23296 KB
in20.txt
AC
209 ms
23296 KB
in21.txt
AC
169 ms
23296 KB
in22.txt
AC
165 ms
23296 KB
in23.txt
AC
178 ms
23296 KB
in24.txt
AC
169 ms
23296 KB
in25.txt
AC
40 ms
10496 KB
in26.txt
AC
40 ms
10496 KB
in27.txt
AC
39 ms
10496 KB
in28.txt
AC
41 ms
10496 KB
in3.txt
AC
211 ms
22656 KB
in4.txt
AC
214 ms
23296 KB
in5.txt
AC
188 ms
22144 KB
in6.txt
AC
215 ms
23296 KB
in7.txt
AC
162 ms
16640 KB
in8.txt
AC
13 ms
8448 KB
in9.txt
AC
218 ms
23296 KB
sample1.txt
AC
4 ms
8448 KB
sample2.txt
AC
3 ms
6400 KB
sample3.txt
AC
4 ms
8448 KB
sample4.txt
AC
4 ms
8448 KB
sub2in1.txt
AC
4 ms
8448 KB
sub2in10.txt
AC
4 ms
8448 KB
sub2in11.txt
AC
4 ms
8448 KB
sub2in12.txt
AC
4 ms
8448 KB
sub2in13.txt
AC
4 ms
8448 KB
sub2in14.txt
AC
4 ms
8448 KB
sub2in15.txt
AC
4 ms
8448 KB
sub2in16.txt
AC
4 ms
8448 KB
sub2in17.txt
AC
4 ms
8448 KB
sub2in18.txt
AC
4 ms
8448 KB
sub2in19.txt
AC
4 ms
8448 KB
sub2in2.txt
AC
4 ms
8448 KB
sub2in20.txt
AC
4 ms
8448 KB
sub2in21.txt
AC
4 ms
8448 KB
sub2in22.txt
AC
4 ms
8448 KB
sub2in23.txt
AC
4 ms
8448 KB
sub2in24.txt
AC
4 ms
8448 KB
sub2in3.txt
AC
4 ms
8448 KB
sub2in4.txt
AC
4 ms
8448 KB
sub2in5.txt
AC
4 ms
8448 KB
sub2in6.txt
AC
4 ms
8448 KB
sub2in7.txt
AC
3 ms
6400 KB
sub2in8.txt
AC
4 ms
8448 KB
sub2in9.txt
AC
4 ms
8448 KB
subin1.txt
AC
422 ms
35840 KB
subin10.txt
AC
404 ms
35840 KB
subin101.txt
AC
302 ms
35840 KB
subin102.txt
AC
284 ms
35712 KB
subin103.txt
AC
264 ms
35584 KB
subin104.txt
AC
260 ms
35584 KB
subin105.txt
AC
248 ms
35712 KB
subin106.txt
AC
260 ms
35712 KB
subin107.txt
AC
289 ms
35840 KB
subin108.txt
AC
278 ms
35712 KB
subin109.txt
AC
284 ms
35712 KB
subin11.txt
AC
389 ms
35840 KB
subin12.txt
AC
397 ms
35840 KB
subin13.txt
AC
408 ms
35840 KB
subin14.txt
AC
400 ms
35840 KB
subin15.txt
AC
395 ms
35584 KB
subin16.txt
AC
401 ms
35584 KB
subin17.txt
AC
350 ms
29184 KB
subin18.txt
AC
353 ms
29184 KB
subin19.txt
AC
367 ms
29184 KB
subin2.txt
AC
383 ms
29056 KB
subin20.txt
AC
362 ms
29056 KB
subin201.txt
AC
4 ms
8448 KB
subin21.txt
AC
55 ms
12544 KB
subin22.txt
AC
55 ms
12544 KB
subin23.txt
AC
57 ms
12544 KB
subin24.txt
AC
55 ms
12544 KB
subin3.txt
AC
423 ms
35840 KB
subin4.txt
AC
346 ms
27136 KB
subin5.txt
AC
389 ms
35840 KB
subin6.txt
AC
306 ms
35840 KB
subin7.txt
AC
19 ms
8448 KB
subin8.txt
AC
14 ms
8448 KB
subin9.txt
AC
419 ms
35840 KB