oj.uz

Submission #55603

# Submission time Handle Problem Language Result Execution time Memory
55603 2018-07-08T07:55:45 Z dennisstar None (KOI17_shell) C++11
100 / 100
 995 ms 186520 KB 
#include <bits/stdc++.h>
int N;
long long sum;
struct data
{
	long long seg[1510]; int lazy[4096];
	data() { int i; for(i=0; i<1510; i++) seg[i]=0; for(i=0;i<4006;i++) lazy[i]=0;}
	void scan() {
		int i;
		for (i=1; i<=N; i++) scanf("%lld",&seg[i]);
	}
	long long val(int a) {
		long long ret=seg[a];
		a+=2047;
		while(a) ret+=(long long)lazy[a], a/=2;
		return ret;
	}
	void gadd(int a, int b, int val) {
		if (a>b) return ;
		if (a%2) lazy[a]+=val, a++;
		if (b%2==0) lazy[b]+=val, b--;
		gadd(a/2,b/2,val);
	}
	void add(int a, int b, int val) {
		a+=2047, b+=2047;
		gadd(a,b,val);
	}
};
data SegTree[1510];
int main()
{
	//freopen("input.txt", "r", stdin);
	scanf("%d", &N);
	int i, j, k, l, m;
	for (i=1; i<=N; i++) for(j=1; j<=N; j++) {scanf("%lld", &SegTree[i].seg[j]);}
	for (i=1; i<=N; i++) for (j=1; j<=N; j++) SegTree[i].seg[j]+=std::max(SegTree[i-1].seg[j],SegTree[i].seg[j-1]), sum+=SegTree[i].seg[j];
	printf("%lld\n", sum);
	char imsi; int x, y;
	for (i=0; i<N; i++) {
		scanf(" %c %d %d", &imsi, &x, &y);
		if (imsi=='U') {
			j=y+1;
			while(j<=N&&SegTree[x].val(j-1)>=SegTree[x-1].val(j))j++;
			sum+=(long long)(j-y);
			m=y;
			SegTree[x].add(y,j-1,1);
			for (k=x+1; k<=N&&m<j; k++) {
				while(m<j&&SegTree[k].val(m-1)>=SegTree[k-1].val(m))m++;
				while(m<j&&j<=N&&SegTree[k].val(j-1)>=SegTree[k-1].val(j))j++;
				SegTree[k].add(m,j-1,1);
				sum+=(long long)j-m;
			}
		}
		else if (imsi=='D') {
			j=y+1;
			while(j<=N&&SegTree[x].val(j-1)>SegTree[x-1].val(j))j++;
			sum-=(long long)(j-y);
			m=y;
			SegTree[x].add(y,j-1,-1);
			for (k=x+1; k<=N&&m<j; k++) {
				while(m<j&&SegTree[k].val(m-1)>=SegTree[k-1].val(m)+1)m++;
				while(m<j&&j<=N&&SegTree[k].val(j-1)>SegTree[k-1].val(j))j++;
				SegTree[k].add(m,j-1,-1);
				sum-=(long long)(j-m);
			}
		}
		printf("%lld\n", sum);
	}
	return 0;
}

Compilation message

shell.cpp: In function 'int main()':
shell.cpp:34:15: warning: unused variable 'l' [-Wunused-variable]
  int i, j, k, l, m;
               ^
shell.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
shell.cpp:35:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i=1; i<=N; i++) for(j=1; j<=N; j++) {scanf("%lld", &SegTree[i].seg[j]);}
                                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
shell.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c %d %d", &imsi, &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 42360 KB Output is correct
2 Correct 37 ms 42520 KB Output is correct
3 Correct 36 ms 42520 KB Output is correct
4 Correct 39 ms 42612 KB Output is correct
5 Correct 39 ms 42716 KB Output is correct
6 Correct 37 ms 42800 KB Output is correct
7 Correct 36 ms 42800 KB Output is correct
8 Correct 37 ms 42808 KB Output is correct
9 Correct 40 ms 42936 KB Output is correct
10 Correct 37 ms 42936 KB Output is correct

Subtask #2
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 43088 KB Output is correct
2 Correct 277 ms 47412 KB Output is correct
3 Correct 286 ms 51896 KB Output is correct
4 Correct 287 ms 56460 KB Output is correct
5 Correct 259 ms 60744 KB Output is correct
6 Correct 290 ms 65156 KB Output is correct
7 Correct 342 ms 69700 KB Output is correct
8 Correct 306 ms 74184 KB Output is correct
9 Correct 280 ms 78444 KB Output is correct
10 Correct 294 ms 82848 KB Output is correct

Subtask #3
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 42360 KB Output is correct
2 Correct 37 ms 42520 KB Output is correct
3 Correct 36 ms 42520 KB Output is correct
4 Correct 39 ms 42612 KB Output is correct
5 Correct 39 ms 42716 KB Output is correct
6 Correct 37 ms 42800 KB Output is correct
7 Correct 36 ms 42800 KB Output is correct
8 Correct 37 ms 42808 KB Output is correct
9 Correct 40 ms 42936 KB Output is correct
10 Correct 321 ms 43088 KB Output is correct
11 Correct 277 ms 47412 KB Output is correct
12 Correct 286 ms 51896 KB Output is correct
13 Correct 287 ms 56460 KB Output is correct
14 Correct 259 ms 60744 KB Output is correct
15 Correct 290 ms 65156 KB Output is correct
16 Correct 342 ms 69700 KB Output is correct
17 Correct 306 ms 74184 KB Output is correct
18 Correct 280 ms 78444 KB Output is correct
19 Correct 294 ms 82848 KB Output is correct
20 Correct 393 ms 91572 KB Output is correct
21 Correct 368 ms 100096 KB Output is correct
22 Correct 532 ms 108632 KB Output is correct
23 Correct 995 ms 117400 KB Output is correct
24 Correct 964 ms 126056 KB Output is correct
25 Correct 922 ms 134764 KB Output is correct
26 Correct 271 ms 138864 KB Output is correct
27 Correct 278 ms 143272 KB Output is correct
28 Correct 356 ms 151936 KB Output is correct
29 Correct 374 ms 160520 KB Output is correct
30 Correct 947 ms 169200 KB Output is correct
31 Correct 941 ms 177972 KB Output is correct
32 Correct 313 ms 182324 KB Output is correct
33 Correct 298 ms 186520 KB Output is correct
34 Correct 37 ms 42936 KB Output is correct