답안 #55603 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
55603	2018-07-08T07:55:45 Z	dennisstar	조개 줍기 (KOI17_shell)	C++11	100 / 100	995 ms	186520 KB

shell

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #55603

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 34.0 / 34.0

Subtask #3 54.0 / 54.0

Subtask #1
12.0 / 12.0

Subtask #2
34.0 / 34.0

Subtask #3
54.0 / 54.0