Submission #1158365
Source Code Expand
#pragma comment(linker, "/STACK:1000000000") #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cstdio> #include <vector> #include <algorithm> #include <string> #include <cstring> #include <queue> #include <deque> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <bitset> #include <memory> #include <cassert> #include <cstdlib> #include <cmath> #include <ctime> #include <stack> #define mp make_pair #define pb push_back typedef long long ll; typedef long double ld; using namespace std; const int MAXN = 200001; int a[MAXN]; int b[MAXN]; ll s[MAXN]; const ll INF = 1000ll * 1000ll * 1000ll * 1000ll * 1000ll * 100ll; struct node { ll mdf; ll val; ll val2; node* l; node* r; }; typedef node* pnode; void setval(pnode t, int l, int r, ll vl) { t->mdf = t->val = vl; t->val2 = vl + l; } pnode newnode(int l, int r) { pnode ans = new node(); setval(ans, l, r, 0); return ans; } void upd(pnode t) { t->val = min(t->l->val, t->r->val); t->val2 = min(t->l->val2, t->r->val2); } void push(pnode t, int l, int r) { int md = (l + r) / 2; if (!(t->l)) t->l = newnode(l, md); if (!(t->r)) t->r = newnode(md + 1, r); if (t->mdf != -1) { setval(t->l, l, md, t->mdf); setval(t->r, md + 1, r, t->mdf); t->mdf = -1; } } pnode root; int n; int k; int lv, rv; ll nval; ll rmq_get(pnode t, int l, int r) { if ((l > rv) || (lv > r)) return INF; if ((lv <= l) && (r <= rv)) return t->val2; push(t, l, r); return min(rmq_get(t->l, l, (l + r) / 2), rmq_get(t->r, (l + r) / 2 + 1, r)); } void rmq_modify(pnode t, int l, int r) { if ((l > rv) || (lv > r)) return; if ((lv <= l) && (r <= rv)) { setval(t, l, r, nval); return; } push(t, l, r); rmq_modify(t->l, l, (l + r) / 2); rmq_modify(t->r, (l + r) / 2 + 1, r); upd(t); } ll g2(int md) { lv = 0, rv = md; ll ans = INF; ans = min(ans, rmq_get(root, 0, k - 1) + k - md); lv = md, rv = k - 1; ans = min(ans, rmq_get(root, 0, k - 1) - md); return ans; } int main() { ios_base::sync_with_stdio(0); // freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); cin >> n >> k; root = newnode(0, k - 1); ll sm = 0; for (int i = 0; i < n; i++) { cin >> a[i] >> b[i]; a[i] *= 2; sm += a[i]; } ll md = 0; for (int i = 0; i < n; i++) { if ((a[i] > k) && (b[i] == 1)) { cout << -1 << endl; return 0; } if (b[i] == 1) { ll val = g2(md); int dlv = (md + 1) % k, drv = (md + a[i] - 1) % k; nval = INF; if (dlv > drv) { lv = 0, rv = drv; rmq_modify(root, 0, k - 1); lv = dlv, rv = k - 1; rmq_modify(root, 0, k - 1); } else { lv = dlv, rv = drv; rmq_modify(root, 0, k - 1); } nval = val; lv = rv = md; rmq_modify(root, 0, k - 1); md = (md + a[i]) % k; } else { md = (md + a[i]) % k; nval = g2(md); lv = rv = md; rmq_modify(root, 0, k - 1); } } if (root->val < INF) cout << sm + root->val << endl; else cout << -1 << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Train Service Planning |
User | cospleermusora |
Language | C++14 (GCC 5.4.1) |
Score | 1700 |
Code Size | 3167 Byte |
Status | AC |
Exec Time | 416 ms |
Memory | 127360 KB |
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 | 1792 KB |
in10.txt | AC | 192 ms | 32640 KB |
in101.txt | AC | 198 ms | 25984 KB |
in102.txt | AC | 211 ms | 40832 KB |
in103.txt | AC | 187 ms | 12544 KB |
in104.txt | AC | 218 ms | 54272 KB |
in105.txt | AC | 222 ms | 60160 KB |
in106.txt | AC | 197 ms | 26112 KB |
in107.txt | AC | 209 ms | 40832 KB |
in108.txt | AC | 188 ms | 12544 KB |
in109.txt | AC | 219 ms | 55296 KB |
in11.txt | AC | 353 ms | 124672 KB |
in110.txt | AC | 223 ms | 60544 KB |
in12.txt | AC | 302 ms | 96384 KB |
in13.txt | AC | 187 ms | 32640 KB |
in14.txt | AC | 355 ms | 124544 KB |
in15.txt | AC | 347 ms | 124544 KB |
in16.txt | AC | 354 ms | 124544 KB |
in17.txt | AC | 354 ms | 124544 KB |
in18.txt | AC | 354 ms | 124672 KB |
in19.txt | AC | 242 ms | 62976 KB |
in2.txt | AC | 306 ms | 96384 KB |
in20.txt | AC | 241 ms | 62976 KB |
in21.txt | AC | 321 ms | 122752 KB |
in22.txt | AC | 304 ms | 113920 KB |
in23.txt | AC | 326 ms | 123776 KB |
in24.txt | AC | 330 ms | 124032 KB |
in25.txt | AC | 35 ms | 1024 KB |
in26.txt | AC | 36 ms | 1024 KB |
in27.txt | AC | 34 ms | 1024 KB |
in28.txt | AC | 38 ms | 1024 KB |
in3.txt | AC | 196 ms | 32768 KB |
in4.txt | AC | 360 ms | 124672 KB |
in5.txt | AC | 312 ms | 108160 KB |
in6.txt | AC | 341 ms | 115072 KB |
in7.txt | AC | 138 ms | 9472 KB |
in8.txt | AC | 186 ms | 60032 KB |
in9.txt | AC | 308 ms | 96384 KB |
sample1.txt | AC | 1 ms | 256 KB |
sample2.txt | AC | 1 ms | 256 KB |
sample3.txt | AC | 1 ms | 256 KB |
sample4.txt | AC | 1 ms | 256 KB |
sub2in1.txt | AC | 2 ms | 640 KB |
sub2in10.txt | AC | 2 ms | 512 KB |
sub2in11.txt | AC | 2 ms | 384 KB |
sub2in12.txt | AC | 1 ms | 384 KB |
sub2in13.txt | AC | 2 ms | 384 KB |
sub2in14.txt | AC | 1 ms | 384 KB |
sub2in15.txt | AC | 1 ms | 256 KB |
sub2in16.txt | AC | 1 ms | 256 KB |
sub2in17.txt | AC | 1 ms | 256 KB |
sub2in18.txt | AC | 1 ms | 256 KB |
sub2in19.txt | AC | 1 ms | 256 KB |
sub2in2.txt | AC | 2 ms | 640 KB |
sub2in20.txt | AC | 1 ms | 256 KB |
sub2in21.txt | AC | 1 ms | 256 KB |
sub2in22.txt | AC | 1 ms | 256 KB |
sub2in23.txt | AC | 1 ms | 256 KB |
sub2in24.txt | AC | 1 ms | 256 KB |
sub2in3.txt | AC | 1 ms | 384 KB |
sub2in4.txt | AC | 1 ms | 384 KB |
sub2in5.txt | AC | 2 ms | 384 KB |
sub2in6.txt | AC | 1 ms | 384 KB |
sub2in7.txt | AC | 1 ms | 256 KB |
sub2in8.txt | AC | 2 ms | 640 KB |
sub2in9.txt | AC | 2 ms | 640 KB |
subin1.txt | AC | 351 ms | 98688 KB |
subin10.txt | AC | 401 ms | 126848 KB |
subin101.txt | AC | 320 ms | 105600 KB |
subin102.txt | AC | 270 ms | 77568 KB |
subin103.txt | AC | 242 ms | 61056 KB |
subin104.txt | AC | 241 ms | 61056 KB |
subin105.txt | AC | 244 ms | 68736 KB |
subin106.txt | AC | 244 ms | 68992 KB |
subin107.txt | AC | 284 ms | 87680 KB |
subin108.txt | AC | 283 ms | 85888 KB |
subin109.txt | AC | 269 ms | 79872 KB |
subin11.txt | AC | 393 ms | 126976 KB |
subin12.txt | AC | 400 ms | 126976 KB |
subin13.txt | AC | 396 ms | 126976 KB |
subin14.txt | AC | 403 ms | 126848 KB |
subin15.txt | AC | 276 ms | 65024 KB |
subin16.txt | AC | 283 ms | 65024 KB |
subin17.txt | AC | 209 ms | 34304 KB |
subin18.txt | AC | 214 ms | 34176 KB |
subin19.txt | AC | 214 ms | 34304 KB |
subin2.txt | AC | 225 ms | 34176 KB |
subin20.txt | AC | 215 ms | 34176 KB |
subin201.txt | AC | 1 ms | 256 KB |
subin21.txt | AC | 38 ms | 1024 KB |
subin22.txt | AC | 39 ms | 1024 KB |
subin23.txt | AC | 40 ms | 1024 KB |
subin24.txt | AC | 38 ms | 1024 KB |
subin3.txt | AC | 416 ms | 126976 KB |
subin4.txt | AC | 352 ms | 110208 KB |
subin5.txt | AC | 380 ms | 117504 KB |
subin6.txt | AC | 402 ms | 127360 KB |
subin7.txt | AC | 350 ms | 97024 KB |
subin8.txt | AC | 170 ms | 27776 KB |
subin9.txt | AC | 410 ms | 126976 KB |