Submission #1871746
Source Code Expand
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long ll ;
#define rep(i, a, b) for (int i = a; i <= b; ++ i)
const int N = 2e5 + 5, inf = 1e9 + 7 ;
using namespace std ;
int na, mo, n = 0, d[N], tr[N << 2] ;
ll fl[N], fr[N] ;
struct poi {
int l, r ;
} a[N] ;
int find(int x) {
int l = 1, r = d[0] ;
for ( ; l <= r ; ) {
int mid = (l + r) / 2 ;
if (d[mid] == x) return mid ;
if (x < d[mid]) r = mid - 1 ; else l = mid + 1 ;
}
return 0 ;
}
void pre() {
d[0] = 0 ;
rep(i, 0, n - 1) d[++ d[0]] = a[i].l, d[++ d[0]] = a[i].r ;
sort(d + 1, d + d[0] + 1) ;
d[0] = unique(d + 1, d + d[0] + 1) - (d + 1) ;
rep(i, 0, n - 1) a[i].l = find(a[i].l), a[i].r = find(a[i].r) ;
}
void build(int p, int l, int r) {
tr[p] = inf ;
if (l == r) return ;
int mid = (l + r) / 2 ;
build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r) ;
}
void modify(int p, int l, int r, int lx, int rx, int ave) {
if (l == lx && r == rx) {
tr[p] = min(tr[p], ave) ;
return ;
}
int mid = (l + r) / 2 ;
if (rx <= mid) modify(p << 1, l, mid, lx, rx, ave) ; else
if (lx > mid) modify(p << 1 | 1, mid + 1, r, lx, rx, ave) ; else
modify(p << 1, l, mid, lx, mid, ave), modify(p << 1 | 1, mid + 1, r, mid + 1, rx, ave) ;
}
int query(int p, int l, int r, int pos) {
int ret = tr[p] ;
if (l == r) return ret ;
int mid = (l + r) / 2 ;
if (pos <= mid) ret = min(ret, query(p << 1, l, mid, pos)) ;
else ret = min(ret, query(p << 1 | 1, mid + 1, r, pos)) ;
return ret ;
}
int main() {
scanf("%d%d", &na, &mo) ;
int x, y, las = 0 ; ll sum = 0 ;
rep(i, 1, na) {
scanf("%d%d", &x, &y) ;
las = (las + x) % mo, sum += x ;
if (x * 2 > mo && (y & 1)) { puts("-1") ; return 0 ; }
if (y & 1) a[n].l = (- 2 * (las - x) % mo + mo) % mo, a[n].r = (- 2 * las % mo + mo) % mo, ++ n ; else
a[n].l = 0, a[n].r = mo - 1, ++ n ;
}
pre() ;
build(1, 1, d[0]) ;
for (int i = n - 1 ; i >= 0; -- i) {
int u = query(1, 1, d[0], a[i].l) ;
if (u == inf) fl[i] = 0 ; else fl[i] = fl[u] + (d[a[u].l] - d[a[i].l] + mo) % mo ;
u = query(1, 1, d[0], a[i].r) ;
if (u == inf) fr[i] = 0 ; else fr[i] = fl[u] + (d[a[u].l] - d[a[i].r] + mo) % mo ;
fl[i] = min(fl[i], fr[i] + (d[a[i].r] - d[a[i].l] + mo) % mo) ;
fr[i] = min(fr[i], fl[i] + (d[a[i].l] - d[a[i].r] + mo) % mo) ;
if (a[i].l <= a[i].r) {
if (a[i].r < d[0]) modify(1, 1, d[0], a[i].r + 1, d[0], i) ;
if (a[i].l > 1) modify(1, 1, d[0], 1, a[i].l - 1, i) ;
} else {
if (a[i].r < a[i].l - 1) modify(1, 1, d[0], a[i].r + 1, a[i].l - 1, i) ;
}
}
ll ans = 1e17 ;
rep(i, 0, n - 1) {
int u = query(1, 1, d[0], a[i].l) ;
if (u == inf) ans = min(ans, 0LL) ; else ans = min(ans, fl[u] + (d[a[u].l] - d[a[i].l] + mo) % mo) ;
u = query(1, 1, d[0], a[i].r) ;
if (u == inf) ans = min(ans, 0LL) ; else ans = min(ans, fl[u] + (d[a[u].l] - d[a[i].r] + mo) % mo) ;
}
printf("%lld\n", ans + sum * 2) ;
return 0 ;
}
Submission Info
Submission Time |
|
Task |
F - Train Service Planning |
User |
mjy0724 |
Language |
C++14 (GCC 5.4.1) |
Score |
1700 |
Code Size |
3031 Byte |
Status |
AC |
Exec Time |
115 ms |
Memory |
8064 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:63:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &na, &mo) ;
^
./Main.cpp:66:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y) ;
^
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 |
3 ms |
6400 KB |
in10.txt |
AC |
83 ms |
8064 KB |
in101.txt |
AC |
66 ms |
8064 KB |
in102.txt |
AC |
65 ms |
8064 KB |
in103.txt |
AC |
64 ms |
8064 KB |
in104.txt |
AC |
65 ms |
8064 KB |
in105.txt |
AC |
64 ms |
8064 KB |
in106.txt |
AC |
66 ms |
8064 KB |
in107.txt |
AC |
65 ms |
8064 KB |
in108.txt |
AC |
64 ms |
8064 KB |
in109.txt |
AC |
64 ms |
8064 KB |
in11.txt |
AC |
84 ms |
8064 KB |
in110.txt |
AC |
64 ms |
8064 KB |
in12.txt |
AC |
82 ms |
8064 KB |
in13.txt |
AC |
80 ms |
8064 KB |
in14.txt |
AC |
82 ms |
8064 KB |
in15.txt |
AC |
80 ms |
8064 KB |
in16.txt |
AC |
81 ms |
8064 KB |
in17.txt |
AC |
82 ms |
8064 KB |
in18.txt |
AC |
82 ms |
8064 KB |
in19.txt |
AC |
80 ms |
8064 KB |
in2.txt |
AC |
84 ms |
8064 KB |
in20.txt |
AC |
81 ms |
8064 KB |
in21.txt |
AC |
72 ms |
8064 KB |
in22.txt |
AC |
69 ms |
8064 KB |
in23.txt |
AC |
74 ms |
8064 KB |
in24.txt |
AC |
74 ms |
8064 KB |
in25.txt |
AC |
34 ms |
8064 KB |
in26.txt |
AC |
33 ms |
8064 KB |
in27.txt |
AC |
33 ms |
8064 KB |
in28.txt |
AC |
34 ms |
8064 KB |
in3.txt |
AC |
83 ms |
8064 KB |
in4.txt |
AC |
85 ms |
8064 KB |
in5.txt |
AC |
71 ms |
7808 KB |
in6.txt |
AC |
81 ms |
8064 KB |
in7.txt |
AC |
78 ms |
8064 KB |
in8.txt |
AC |
11 ms |
640 KB |
in9.txt |
AC |
84 ms |
8064 KB |
sample1.txt |
AC |
2 ms |
6400 KB |
sample2.txt |
AC |
1 ms |
256 KB |
sample3.txt |
AC |
2 ms |
6400 KB |
sample4.txt |
AC |
2 ms |
6400 KB |
sub2in1.txt |
AC |
2 ms |
6400 KB |
sub2in10.txt |
AC |
2 ms |
6400 KB |
sub2in11.txt |
AC |
2 ms |
6400 KB |
sub2in12.txt |
AC |
2 ms |
6400 KB |
sub2in13.txt |
AC |
2 ms |
6400 KB |
sub2in14.txt |
AC |
2 ms |
6400 KB |
sub2in15.txt |
AC |
2 ms |
6400 KB |
sub2in16.txt |
AC |
2 ms |
6400 KB |
sub2in17.txt |
AC |
2 ms |
6400 KB |
sub2in18.txt |
AC |
2 ms |
6400 KB |
sub2in19.txt |
AC |
2 ms |
6400 KB |
sub2in2.txt |
AC |
2 ms |
6400 KB |
sub2in20.txt |
AC |
2 ms |
6400 KB |
sub2in21.txt |
AC |
2 ms |
6400 KB |
sub2in22.txt |
AC |
2 ms |
6400 KB |
sub2in23.txt |
AC |
2 ms |
6400 KB |
sub2in24.txt |
AC |
2 ms |
6400 KB |
sub2in3.txt |
AC |
2 ms |
6400 KB |
sub2in4.txt |
AC |
2 ms |
6400 KB |
sub2in5.txt |
AC |
2 ms |
6400 KB |
sub2in6.txt |
AC |
2 ms |
6400 KB |
sub2in7.txt |
AC |
1 ms |
256 KB |
sub2in8.txt |
AC |
2 ms |
6400 KB |
sub2in9.txt |
AC |
2 ms |
6400 KB |
subin1.txt |
AC |
114 ms |
8064 KB |
subin10.txt |
AC |
112 ms |
8064 KB |
subin101.txt |
AC |
90 ms |
8064 KB |
subin102.txt |
AC |
76 ms |
8064 KB |
subin103.txt |
AC |
72 ms |
8064 KB |
subin104.txt |
AC |
70 ms |
8064 KB |
subin105.txt |
AC |
64 ms |
8064 KB |
subin106.txt |
AC |
63 ms |
8064 KB |
subin107.txt |
AC |
75 ms |
8064 KB |
subin108.txt |
AC |
83 ms |
8064 KB |
subin109.txt |
AC |
75 ms |
8064 KB |
subin11.txt |
AC |
107 ms |
8064 KB |
subin12.txt |
AC |
109 ms |
8064 KB |
subin13.txt |
AC |
110 ms |
8064 KB |
subin14.txt |
AC |
111 ms |
8064 KB |
subin15.txt |
AC |
109 ms |
8064 KB |
subin16.txt |
AC |
110 ms |
8064 KB |
subin17.txt |
AC |
104 ms |
8064 KB |
subin18.txt |
AC |
107 ms |
8064 KB |
subin19.txt |
AC |
108 ms |
8064 KB |
subin2.txt |
AC |
113 ms |
8064 KB |
subin20.txt |
AC |
109 ms |
8064 KB |
subin201.txt |
AC |
2 ms |
6400 KB |
subin21.txt |
AC |
33 ms |
8064 KB |
subin22.txt |
AC |
33 ms |
8064 KB |
subin23.txt |
AC |
33 ms |
8064 KB |
subin24.txt |
AC |
34 ms |
8064 KB |
subin3.txt |
AC |
115 ms |
8064 KB |
subin4.txt |
AC |
97 ms |
7808 KB |
subin5.txt |
AC |
109 ms |
8064 KB |
subin6.txt |
AC |
82 ms |
8064 KB |
subin7.txt |
AC |
18 ms |
1024 KB |
subin8.txt |
AC |
13 ms |
768 KB |
subin9.txt |
AC |
114 ms |
8064 KB |