oj.uz

Submission #403713

# Submission time Handle Problem Language Result Execution time Memory
403713 2021-05-13T11:35:19 Z jamezzz None (KOI17_shell) C++14
100 / 100
 754 ms 35528 KB 
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#include <ext/rope>
using namespace __gnu_cxx;

typedef tree<long long, null_type, less<long long>,
rb_tree_tag, tree_order_statistics_node_update> pbds;
//less_equal for identical elements

//#define DEBUG

#ifdef DEBUG
#define debug(...) printf(__VA_ARGS__);
#else
#define debug(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;

int n,a[1505][1505],x,y;
char t;
ll s=0,ft[1505][1505];

void up(int r,int c,ll v){
	while(c<=n){
		ft[r][c]+=v;
		c+=c&-c;
	}
}

ll qry(int r,int c){
	ll res=0;
	while(c){
		res+=ft[r][c];
		c-=c&-c;
	}
	return res;
}

int main(){
	sf("%d",&n);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			sf("%d",&a[i][j]);
			ll dp=a[i][j]+max(qry(i-1,j),qry(i,j-1));
			up(i,j,dp);
			up(i,j+1,-dp);
			s+=dp;
		}
	}
	pf("%lld\n",s);
	for(int i=0;i<n;++i){
		sf(" %c",&t);
		sf("%d%d",&x,&y);
		int add;
		if(t=='U')add=1;
		else add=-1;
		a[x][y]+=add;
		int cl=y,cr=y;
		for(int r=x;r<=n;++r){
			while(cl<cr){
				ll pv=qry(r,cl);
				ll nw=a[r][cl]+max(qry(r,cl-1),qry(r-1,cl));
				if(pv==nw)++cl;
				else break;
			}
			up(r,cl,add);
			while(cr<=n){
				ll pv=qry(r,cr)-add;
				ll nw=a[r][cr]+max(qry(r,cr-1),qry(r-1,cr));
				if(pv!=nw)++cr;
				else break;
			}
			//pf("%d %d %d\n",r,cl,cr);
			up(r,cr,-add);
			s+=(cr-cl)*add;
			if(cr==cl)break;
		}
		/*
		for(int r=1;r<=n;++r){
			for(int c=1;c<=n;++c){
				pf("%lld ",qry(r,c));
			}
			pf("\n");
		}
		*/
		pf("%lld\n",s);
	}
}

/*
3
3 1 1
1 1 1
1 1 1
U 2 1
U 1 2
U 1 2
*/

Compilation message

shell.cpp: In function 'int main()':
shell.cpp:62:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |  sf("%d",&n);
      |    ^
shell.cpp:65:6: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |    sf("%d",&a[i][j]);
      |      ^
shell.cpp:74:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |   sf(" %c",&t);
      |     ^
shell.cpp:75:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |   sf("%d%d",&x,&y);
      |     ^

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1100 KB Output is correct
2 Correct 3 ms 1100 KB Output is correct
3 Correct 3 ms 1228 KB Output is correct
4 Correct 4 ms 1100 KB Output is correct
5 Correct 4 ms 1280 KB Output is correct
6 Correct 3 ms 1100 KB Output is correct
7 Correct 3 ms 1228 KB Output is correct
8 Correct 3 ms 1100 KB Output is correct
9 Correct 4 ms 1280 KB Output is correct
10 Correct 3 ms 1228 KB Output is correct

Subtask #2
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 26780 KB Output is correct
2 Correct 320 ms 30848 KB Output is correct
3 Correct 327 ms 30772 KB Output is correct
4 Correct 317 ms 30888 KB Output is correct
5 Correct 312 ms 30872 KB Output is correct
6 Correct 390 ms 30960 KB Output is correct
7 Correct 320 ms 30836 KB Output is correct
8 Correct 350 ms 30800 KB Output is correct
9 Correct 307 ms 30764 KB Output is correct
10 Correct 309 ms 30760 KB Output is correct

Subtask #3
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1100 KB Output is correct
2 Correct 3 ms 1100 KB Output is correct
3 Correct 3 ms 1228 KB Output is correct
4 Correct 4 ms 1100 KB Output is correct
5 Correct 4 ms 1280 KB Output is correct
6 Correct 3 ms 1100 KB Output is correct
7 Correct 3 ms 1228 KB Output is correct
8 Correct 3 ms 1100 KB Output is correct
9 Correct 4 ms 1280 KB Output is correct
10 Correct 350 ms 26780 KB Output is correct
11 Correct 320 ms 30848 KB Output is correct
12 Correct 327 ms 30772 KB Output is correct
13 Correct 317 ms 30888 KB Output is correct
14 Correct 312 ms 30872 KB Output is correct
15 Correct 390 ms 30960 KB Output is correct
16 Correct 320 ms 30836 KB Output is correct
17 Correct 350 ms 30800 KB Output is correct
18 Correct 307 ms 30764 KB Output is correct
19 Correct 309 ms 30760 KB Output is correct
20 Correct 3 ms 1228 KB Output is correct
21 Correct 360 ms 30992 KB Output is correct
22 Correct 425 ms 31496 KB Output is correct
23 Correct 357 ms 31488 KB Output is correct
24 Correct 684 ms 31528 KB Output is correct
25 Correct 613 ms 35528 KB Output is correct
26 Correct 587 ms 35392 KB Output is correct
27 Correct 331 ms 31196 KB Output is correct
28 Correct 321 ms 31220 KB Output is correct
29 Correct 400 ms 35336 KB Output is correct
30 Correct 353 ms 35400 KB Output is correct
31 Correct 610 ms 35316 KB Output is correct
32 Correct 754 ms 35400 KB Output is correct
33 Correct 332 ms 31188 KB Output is correct
34 Correct 369 ms 31148 KB Output is correct