| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 782579 |
2023-07-14T06:00:29 Z |
qwerasdfzxcl |
케이크 (JOI13_cake) |
C++17 |
|
283 ms |
85600 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<int, ll> mp[300300];
int n, a[300300];
ll sumE[600600], sumO[600600];
struct Seg{
int tree[2002000];
void init(int i, int l, int r){
if (l==r){
tree[i] = a[l];
return;
}
int m = (l+r)>>1;
init(i<<1, l, m); init(i<<1|1, m+1, r);
tree[i] = min(tree[i<<1], tree[i<<1|1]);
}
int prefix(int i, int l, int r, int s, int x){
if (r<s) return -1;
if (tree[i] > x) return -1;
if (l==r) return l;
int m = (l+r)>>1;
int ret = prefix(i<<1, l, m, s, x);
if (ret!=-1) return ret;
return prefix(i<<1|1, m+1, r, s, x);
}
int suffix(int i, int l, int r, int e, int x){
// printf(" suffix %d %d %d %d %d / = %d\n", i, l, r, e, x, tree[i]);
if (e<l) return -1;
if (tree[i] > x) return -1;
if (l==r) return l;
int m = (l+r)>>1;
int ret = suffix(i<<1|1, m+1, r, e, x);
if (ret!=-1) return ret;
return suffix(i<<1, l, m, e, x);
}
}tree;
inline int dist(int s, int e){
return (n+e-s) % n;
}
pair<int, int> getL(int l, int r, int typ){
// naive
// while(a[l] > a[r]){
// l++;
// typ ^= 1;
// if (l>=n) l = 0;
// }
// return {l, typ};
int ret = -1;
if (l <= r){
ret = tree.prefix(1, 0, n-1, l, a[r]);
}
else{
ret = tree.prefix(1, 0, n-1, l, a[r]);
if (ret==-1) ret = tree.prefix(1, 0, n-1, 0, a[r]);
}
assert(ret!=-1);
typ ^= dist(l, ret) % 2;
return {ret, typ};
}
pair<int, int> getR(int l, int r, int typ){
// naive
// while(a[l] < a[r]){
// r--;
// typ ^= 1;
// if (r<0) r = n-1;
// }
// return {r, typ};
int ret = -1;
if (l <= r){
ret = tree.suffix(1, 0, n-1, r, a[l]);
}
else{
ret = tree.suffix(1, 0, n-1, r, a[l]);
if (ret==-1) ret = tree.suffix(1, 0, n-1, n-1, a[l]);
}
assert(ret!=-1);
typ ^= dist(ret, r) % 2;
return {ret, typ};
}
ll sumL(int l, int r, int typ){
// naive
// ll ret = 0;
// for (int i=l;;i=(i+1)%n){
// if (typ) ret += a[i];
// typ ^= 1;
// if (i==r) break;
// }
// return ret;
if (r<l) r += n;
if ((l%2==0 && typ==1) || (l%2==1 && typ==0)) return sumE[r] - ((l==0)?0:sumE[l-1]);
return sumO[r] - ((l==0)?0:sumO[l-1]);
}
ll sumR(int r, int l, int typ){
// naive
// ll ret = 0;
// for (int i=r;;i=(n+i-1)%n){
// if (typ) ret += a[i];
// typ ^= 1;
// if (i==l) break;
// }
// // printf(" ok %lld\n", ret);
// return ret;
if (r<l) r += n;
if ((r%2==0 && typ==1) || (r%2==1 && typ==0)) return sumE[r] - ((l==0)?0:sumE[l-1]);
return sumO[r] - ((l==0)?0:sumO[l-1]);
}
ll dfs(int l, int r, int typ){
// printf(" call %d %d %d\n", l, r, typ);
if (l==r) return (typ)?a[l]:0;
if (mp[l].find(r)!=mp[l].end()) return mp[l][r];
ll &ret = mp[l][r];
if (a[l] > a[r]){
auto [nl, nt] = getL(l, r, typ);
// printf(" ok add %lld\n", sumL(l, (n+nl-1)%n, typ));
return ret = sumL(l, (n+nl-1)%n, typ) + dfs(nl, r, nt);
}
auto [nr, nt] = getR(l, r, typ);
// printf(" ok add %lld\n", sumR(r, (n+nr+1)%n, typ));
return ret = sumR(r, (n+nr+1)%n, typ) + dfs(l, nr, nt);
}
int main(){
scanf("%d", &n);
for (int i=0;i<n;i++) scanf("%d", a+i);
for (int i=0;i<n*2;i++){
ll val = (i<n)?a[i]:a[i-n];
if (i==0) sumE[i] = val;
else if (i%2==0) sumE[i] = sumE[i-1] + val;
else sumE[i] = sumE[i-1];
if (i==0) sumO[i] = 0;
else if (i%2==1) sumO[i] = sumO[i-1] + val;
else sumO[i] = sumO[i-1];
}
tree.init(1, 0, n-1);
for (int i=0;i<n;i++){
int l = (n+i+1) % n, r = (n+i-1) % n;
printf("%lld\n", a[i] + dfs(l, r, 0));
}
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:156:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
156 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
cake.cpp:157:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
157 | for (int i=0;i<n;i++) scanf("%d", a+i);
| ~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
15444 KB |
Output is correct |
| 2 |
Correct |
10 ms |
15324 KB |
Output is correct |
| 3 |
Correct |
10 ms |
15512 KB |
Output is correct |
| 4 |
Correct |
11 ms |
15432 KB |
Output is correct |
| 5 |
Correct |
9 ms |
15316 KB |
Output is correct |
| 6 |
Correct |
9 ms |
15316 KB |
Output is correct |
| 7 |
Correct |
9 ms |
15316 KB |
Output is correct |
| 8 |
Correct |
10 ms |
15444 KB |
Output is correct |
| 9 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 10 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 11 |
Correct |
9 ms |
14420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
72 ms |
35152 KB |
Output is correct |
| 2 |
Correct |
66 ms |
33956 KB |
Output is correct |
| 3 |
Correct |
76 ms |
35532 KB |
Output is correct |
| 4 |
Correct |
170 ms |
64988 KB |
Output is correct |
| 5 |
Correct |
145 ms |
57688 KB |
Output is correct |
| 6 |
Correct |
221 ms |
80352 KB |
Output is correct |
| 7 |
Correct |
283 ms |
85600 KB |
Output is correct |
| 8 |
Correct |
215 ms |
80024 KB |
Output is correct |
| 9 |
Correct |
240 ms |
80240 KB |
Output is correct |
| 10 |
Correct |
274 ms |
74056 KB |
Output is correct |
| 11 |
Correct |
212 ms |
80620 KB |
Output is correct |
| 12 |
Correct |
208 ms |
74832 KB |
Output is correct |
| 13 |
Correct |
176 ms |
74928 KB |
Output is correct |
| 14 |
Correct |
238 ms |
74104 KB |
Output is correct |
| 15 |
Correct |
205 ms |
78152 KB |
Output is correct |
