Submission #349117
Source Code Expand
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
typedef long long ll;
/*
RBSTで書かれたStarry Sky Tree
*/
struct STree {
using D = ll;
const static D INF = 1LL<<55;
struct Node;
using NP = Node*;
static Node last_d;
static NP last;
struct Node {
NP l, r;
int sz;
D v, mi, lz;
Node(D v) :l(last), r(last), sz(1), v(v), mi(v), lz(0) {}
Node() :l(nullptr), r(nullptr), sz(0) {} //last用
void push() {
assert(this != last);
if (lz) {
if (l->sz) {
l->lzdata(lz);
}
if (r->sz) {
r->lzdata(lz);
}
lz = 0;
}
}
void lzdata(D d) {
v += d;
mi += d;
lz += d;
}
NP update() {
assert(this != last);
sz = 1+l->sz+r->sz;
assert(!lz);
mi = v;
if (l->sz) {
mi = min(mi, l->mi);
}
if (r->sz) {
mi = min(mi, r->mi);
}
return this;
}
D get(int a, int b) {
if (!sz || b <= 0 || sz <= a) return INF;
if (a <= 0 && sz <= b) return mi;
push();
D res = INF;
if (a <= l->sz && l->sz < b) res = min(res, v);
res = min(res, l->get(a, b));
res = min(res, r->get(a- l->sz - 1, b- l->sz - 1));
return res;
}
void add(int a, int b, D x) {
if (!sz || b <= 0 || sz <= a) return;
if (a <= 0 && sz <= b) {
lzdata(x);
return;
}
push();
l->add(a, b, x);
if (a <= l->sz && l->sz < b) {
v += x;
}
r->add(a- l->sz - 1, b- l->sz - 1, x);
update();
}
} *n;
static NP built(int sz, D d[]) {
if (!sz) return last;
int md = sz/2;
NP x = new Node(d[md]);
x->l = built(md, d);
x->r = built(sz-(md+1), d+(md+1));
return x->update();
}
static uint xor128(){
static uint x=123456789,y=362436069,z=521288629,w=88675123;
uint t;
t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}
static NP merge(NP l, NP r) {
if (!l->sz) return r;
if (!r->sz) return l;
l->push(); r->push();
if ((int)(xor128() % (l->sz + r->sz)) < l->sz) {
l->r = merge(l->r, r);
return l->update();
} else {
r->l = merge(l, r->l);
return r->update();
}
}
static pair<NP, NP> split(NP x, int k) {
if (!x->sz) return {last, last};
x->push();
if (k <= x->l->sz) {
auto y = split(x->l, k);
x->l = y.second;
y.second = x->update();
return y;
} else {
auto y = split(x->r, k- x->l->sz -1);
x->r = y.first;
y.first = x->update();
return y;
}
}
STree() : n(last) {}
STree(NP n) : n(n) {}
STree(D d) : n(new Node(d)) {}
STree(int sz, D d[]) {
n = built(sz, d);
}
int sz() {
return n->sz;
}
void merge(STree r) {
n = merge(n, r.n);
}
STree split(int k) {
auto u = split(n, k);
n = u.first;
return STree(u.second);
}
void insert(int k, D x) {
auto u = split(n, k);
n = merge(merge(u.first, new Node(x)), u.second);
}
void erase(int k) {
auto u = split(n, k);
n = merge(u.first, split(u.second, 1).second);
}
void add(int l, int r, D x) {
return n->add(l, r, x);
}
D get(int l, int r) {
return n->get(l, r);
}
};
STree::Node STree::last_d = STree::Node();
STree::NP STree::last = &last_d;
const int MN = 100200;
//int d[MN];
ll mi[MN];
ll r;
ll s[MN*2];
ll offset;
void input() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%lld", s+i);
}
if (n % 2) {
s[n] = 1LL<<55;
offset -= 1LL<<55;
n++;
}
offset += s[0];
r = 0;
s[0] = 0;
mi[n/2] = 1LL<<55;
for (int i = n/2-1; i >= 0; i--) {
mi[i] = min(s[i*2], min(s[i*2+1], mi[i+1]));
offset += s[i*2];
}
for (int i = n/2-1; i >= 0; i--) {
if (s[i*2] < min(s[i*2+1], mi[i+1])) {
r += min(s[i*2+1], mi[i+1]) - s[i*2];
}
}
}
int main() {
input();
printf("%lld\n", r+offset);
int q;
scanf("%d", &q);
assert(!q);
for (int i = 0; i < q; i++) {
int p; ll d;
scanf("%d %lld", &p, &d); p--;
int q = p/2;
r -= max(s[q*2], min(s[q*2+1], mi[q+1]));
s[p] -= d;
r += max(s[q*2], min(s[q*2+1], mi[q+1]));
ll mib = min(s[q*2], min(s[q*2+1], mi[q+1]));
if (mi[q] == mib) {
printf("%lld\n", r);
}
}
}
Submission Info
Submission Time |
|
Task |
D - コインの取り合い |
User |
yosupo |
Language |
C++11 (GCC 4.8.1) |
Score |
10 |
Code Size |
5345 Byte |
Status |
RE |
Exec Time |
329 ms |
Memory |
3732 KB |
Compile Error
./Main.cpp: In function ‘void input()’:
./Main.cpp:170:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
./Main.cpp:172:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", s+i);
^
./Main.cpp: In function ‘int main()’:
./Main.cpp:199:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
^
./Main.cpp:203:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %lld", &p, &d); p--;
^
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Subtask3 |
Score / Max Score |
0 / 0 |
10 / 10 |
0 / 80 |
0 / 90 |
Status |
|
|
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt |
Subtask1 |
subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt |
Subtask2 |
sample_01.txt, sample_02.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt |
Subtask3 |
subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt, subtask3_08.txt, subtask3_09.txt, subtask3_10.txt, subtask3_11.txt, subtask3_12.txt, subtask3_13.txt, subtask3_14.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
RE |
271 ms |
1244 KB |
sample_02.txt |
RE |
270 ms |
1244 KB |
subtask1_01.txt |
AC |
28 ms |
1248 KB |
subtask1_02.txt |
AC |
78 ms |
3552 KB |
subtask1_03.txt |
AC |
65 ms |
3040 KB |
subtask1_04.txt |
AC |
77 ms |
3552 KB |
subtask1_05.txt |
AC |
77 ms |
3548 KB |
subtask1_06.txt |
AC |
58 ms |
3556 KB |
subtask1_07.txt |
AC |
74 ms |
3556 KB |
subtask2_01.txt |
RE |
271 ms |
1248 KB |
subtask2_02.txt |
RE |
298 ms |
2400 KB |
subtask2_03.txt |
RE |
311 ms |
3548 KB |
subtask2_04.txt |
RE |
308 ms |
3680 KB |
subtask2_05.txt |
RE |
312 ms |
3680 KB |
subtask2_06.txt |
RE |
313 ms |
3676 KB |
subtask2_07.txt |
RE |
307 ms |
3676 KB |
subtask2_08.txt |
AC |
59 ms |
3544 KB |
subtask2_09.txt |
RE |
290 ms |
2020 KB |
subtask2_10.txt |
RE |
314 ms |
3680 KB |
subtask2_11.txt |
RE |
313 ms |
3548 KB |
subtask2_12.txt |
RE |
309 ms |
3732 KB |
subtask3_01.txt |
RE |
292 ms |
1884 KB |
subtask3_02.txt |
RE |
318 ms |
3684 KB |
subtask3_03.txt |
RE |
329 ms |
3676 KB |
subtask3_04.txt |
RE |
329 ms |
3680 KB |
subtask3_05.txt |
AC |
57 ms |
3556 KB |
subtask3_06.txt |
RE |
326 ms |
3708 KB |
subtask3_07.txt |
RE |
324 ms |
3660 KB |
subtask3_08.txt |
RE |
322 ms |
3676 KB |
subtask3_09.txt |
RE |
323 ms |
3620 KB |
subtask3_10.txt |
RE |
314 ms |
3684 KB |
subtask3_11.txt |
RE |
306 ms |
2532 KB |
subtask3_12.txt |
RE |
325 ms |
3680 KB |
subtask3_13.txt |
RE |
328 ms |
3600 KB |
subtask3_14.txt |
RE |
325 ms |
3684 KB |