| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 403475 |
2021-05-13T08:27:12 Z |
tqbfjotld |
None (KOI17_shell) |
C++14 |
|
805 ms |
317932 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
set<int> ups[1505];
int fenwick[1505][1505];
void upd(int pos, int val, int num){
while (pos<1505){
fenwick[pos][num]+=val;
pos+=pos&-pos;
}
}
int qu(int pos, int num){
int ans = 0;
while (pos>0){
ans += fenwick[pos][num];
pos-=pos&-pos;
}
return ans;
}
int initarr[1505][1505];
int v2[1505][1505];
int n;
int curans = 0;
vector<pair<int,int> > to_up;
vector<pair<int,int> > to_left;
void incr(int x, int y){
int curval = qu(x,y);
if (x!=1 && y!=n){
int t1 = qu(x-1,y+1);
if (t1==curval+1){
to_up.push_back({x,y+1});
}
}
if (x!=n && y!=1){
int t2 = qu(x+1,y-1);
if (t2==curval){
//printf("pushing %lld %lld\n",x+1,y);
to_left.push_back({x+1,y});
incr(x+1,y);
}
}
}
void decr(int x, int y){
int curval = qu(x,y);
if (x!=1 && y!=n){
int t1 = qu(x-1,y+1);
if (t1==curval){
to_left.push_back({x,y+1});
}
}
if (x!=n && y!=1){
int t2 = qu(x+1,y-1);
if (t2==curval-1){
to_up.push_back({x+1,y});
decr(x+1,y);
}
}
}
void set_up(int x, int y){
//printf("%lld %lld set up\n",x,y);
assert(ups[y].lower_bound(x)==ups[y].end() || (*ups[y].lower_bound(x))!=x);
assert(y!=1);
ups[y].insert(x);
}
void set_left(int x, int y){
//printf("%lld %lld set left\n",x,y);
assert((*ups[y].lower_bound(x))==x);
assert(x!=1);
ups[y].erase(ups[y].lower_bound(x));
}
void incr2(int x, int y, int minbound){
auto it = ups[y].lower_bound(minbound+1);
int bound;
if (it==ups[y].end()){
bound = n;
}
else bound = (*it)-1;
curans += bound-x+1;
upd(x,1,y);
upd(bound+1,-1,y);
if (y!=n){
auto it2 = ups[y+1].lower_bound(x);
if (it2==ups[y+1].end() || (*it2)>bound) return;
incr2((*it2),y+1,bound);
}
}
void decr2(int x, int y, int minbound){
auto it = ups[y].lower_bound(minbound+1);
int bound;
if (it==ups[y].end()){
bound = n;
}
else bound = (*it)-1;
curans -= bound-x+1;
upd(x,-1,y);
upd(bound+1,1,y);
if (y!=n){
auto it2 = ups[y+1].lower_bound(x);
if (it2==ups[y+1].end() || (*it2)>bound) return;
decr2((*it2),y+1,bound);
}
}
main(){
scanf("%lld",&n);
for (int x = 1; x<=n; x++){
for (int y = 1; y<=n; y++){
scanf("%lld",&initarr[x][y]);
}
}
for (int x = 1; x<=n; x++){
for (int y = 1; y<=n; y++){
if (x==1&&y==1){
v2[x][y] = initarr[x][y];
}
else if (x==1){
v2[x][y] = v2[x][y-1]+initarr[x][y];
ups[y].insert(x);
}
else if (y==1){
v2[x][y] = v2[x-1][y]+initarr[x][y];
}
else if (v2[x-1][y]>v2[x][y-1]){
v2[x][y] = v2[x-1][y]+initarr[x][y];
}
else{
v2[x][y] = v2[x][y-1]+initarr[x][y];
ups[y].insert(x);
}
curans += v2[x][y];
upd(x,v2[x][y],y);
upd(x+1,-v2[x][y],y);
}
}
printf("%lld\n",curans);
for (int q = 0; q<n; q++){
char c;
int a,b;
scanf(" %c",&c);
scanf("%lld%lld",&a,&b);
if (c=='U'){
incr(a,b);
//printf("incr donw\n");
for (auto x : to_left){
set_left(x.first,x.second);
}
incr2(a,b,a);
for (auto x : to_up){
set_up(x.first,x.second);
}
}
else{
decr(a,b);
for (auto x : to_left){
set_left(x.first,x.second);
}
decr2(a,b,a);
for (auto x : to_up){
set_up(x.first,x.second);
}
}
to_left.clear();
to_up.clear();
printf("%lld\n",curans);
}
}
Compilation message
shell.cpp:111:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
111 | main(){
| ^~~~
shell.cpp: In function 'int main()':
shell.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
112 | scanf("%lld",&n);
| ~~~~~^~~~~~~~~~~
shell.cpp:115:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
115 | scanf("%lld",&initarr[x][y]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
shell.cpp:146:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
146 | scanf(" %c",&c);
| ~~~~~^~~~~~~~~~
shell.cpp:147:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
147 | scanf("%lld%lld",&a,&b);
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1996 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
1996 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
805 ms |
317932 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1996 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
1996 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
