oj.uz

Submission #284270

# Submission time Handle Problem Language Result Execution time Memory
284270 2020-08-27T06:33:00 Z 송준혁(#5749) Progression (NOI20_progression) C++17
55 / 100
 1245 ms 55120 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, Q;
int A[303030];
bool ISS;

struct Node{
	LL l, r, sum, lz;
	int ld, rd, ans;
	bool iss, fl;
} T[1202020], I;

Node add(Node a, Node b){
	if (a.ld == 0) return b;
	if (b.ld == 0) return a;
	Node ret;
	ret.lz = 0, ret.iss = false;
	ret.sum = a.sum + b.sum;
	ret.l = a.l, ret.r = b.r;
	ret.ans = max(a.ans, b.ans);
	if (a.r == b.l) ret.ans = max(ret.ans, a.rd+b.ld);
	ret.ld = a.ld + ((a.fl && a.l == b.l)?b.ld:0);
	ret.rd = b.rd + ((b.fl && a.r == b.r)?a.rd:0);
	ret.fl = a.fl && b.fl && a.l == b.l;
	return ret;
}

void busy(int id, int s, int e){
	if (T[id].iss){
		T[id].fl = true;
		T[id].l = T[id].r = T[id].lz;
		T[id].sum = T[id].lz*(e-s+1);
		T[id].ld = T[id].rd = T[id].ans = e-s+1;
		if (s != e){
			T[id*2].lz = T[id*2+1].lz = T[id].lz;
			T[id*2].iss = T[id*2+1].iss = true;
		}
	}
	else{
		T[id].l += T[id].lz, T[id].r += T[id].lz;
		T[id].sum += T[id].lz*(e-s+1);
		if (s != e) T[id*2].lz += T[id].lz, T[id*2+1].lz += T[id].lz;
	}
	T[id].lz = 0, T[id].iss = false;
}

void init(int id, int s, int e){
	if (s == e){
		T[id].l = T[id].r = T[id].sum = A[s]-A[s-1];
		T[id].ld = T[id].rd = T[id].ans = 1;
		T[id].fl = true, T[id].iss = false;
		T[id].lz = 0;
		return;
	}
	int m=s+e>>1;
	init(id*2, s, m), init(id*2+1, m+1, e);
	T[id] = add(T[id*2], T[id*2+1]);
}

void upd(int id, int s, int e, int ts, int te, int v){
	if (e < ts || te < s) return;
	if (ts <= s && e <= te){
		if (ISS) T[id].lz = v, T[id].iss = true;
		else T[id].lz += v;
		busy(id, s, e);
		return;
	}
	busy(id, s, e);
	int m=s+e>>1;
	upd(id*2, s, m, ts, te, v);
	upd(id*2+1, m+1, e, ts, te, v);
	T[id] = add(T[id*2], T[id*2+1]);
}

LL sumq(int id, int s, int e, int ts, int te){
	if (e < ts || te < s) return 0;
	busy(id, s, e);
	if (ts <= s && e <= te) return T[id].sum;
	int m=s+e>>1;
	return sumq(id*2, s, m, ts, te)+sumq(id*2+1, m+1, e, ts, te);
}

Node nodq(int id, int s, int e, int ts, int te){
	if (e < ts || te < s) return I;
	busy(id, s, e);
	if (ts <= s && e <= te) return T[id];
	int m=s+e>>1;
	return add(nodq(id*2, s, m, ts, te), nodq(id*2+1, m+1, e, ts, te));
}

int main(){
	scanf("%d %d", &N, &Q);
	for (int i=1; i<=N; i++) scanf("%d", &A[i]);
	init(1, 1, N);
	while (Q--){
		int l, r;
		LL s, c;
		scanf("%d", &l);
		if (l == 1){
			scanf("%d %d %lld %lld", &l, &r, &s, &c);
			ISS = false;
			upd(1, 1, N, l, l, s);
			upd(1, 1, N, l+1, r, c);
			upd(1, 1, N, r+1, r+1, -(s+c*(r-l)));
		}
		else if (l == 2){
			scanf("%d %d %lld %lld", &l, &r, &s, &c);
			ISS = true;
			LL x = sumq(1, 1, N, 1, r+1);
			upd(1, 1, N, r+1, r+1, x-(s+c*(r-l)));
			x = sumq(1, 1, N, 1, l-1);
			upd(1, 1, N, l, l, s-x);
			upd(1, 1, N, l+1, r, c);
		}
		else{
			scanf("%d %d", &l, &r);
			printf("%d\n", nodq(1, 1, N, l+1, r).ans+1);
		}
	}
	return 0;
}

Compilation message

Progression.cpp: In function 'void init(int, int, int)':
Progression.cpp:58:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |  int m=s+e>>1;
      |        ~^~
Progression.cpp: In function 'void upd(int, int, int, int, int, int)':
Progression.cpp:72:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |  int m=s+e>>1;
      |        ~^~
Progression.cpp: In function 'LL sumq(int, int, int, int, int)':
Progression.cpp:82:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |  int m=s+e>>1;
      |        ~^~
Progression.cpp: In function 'Node nodq(int, int, int, int, int)':
Progression.cpp:90:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |  int m=s+e>>1;
      |        ~^~
Progression.cpp: In function 'int main()':
Progression.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |  scanf("%d %d", &N, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~
Progression.cpp:96:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   96 |  for (int i=1; i<=N; i++) scanf("%d", &A[i]);
      |                           ~~~~~^~~~~~~~~~~~~
Progression.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  101 |   scanf("%d", &l);
      |   ~~~~~^~~~~~~~~~
Progression.cpp:103:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |    scanf("%d %d %lld %lld", &l, &r, &s, &c);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:110:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  110 |    scanf("%d %d %lld %lld", &l, &r, &s, &c);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:119:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  119 |    scanf("%d %d", &l, &r);
      |    ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 677 ms 51964 KB Output is correct
2 Correct 256 ms 888 KB Output is correct
3 Correct 249 ms 888 KB Output is correct
4 Correct 262 ms 888 KB Output is correct
5 Correct 251 ms 992 KB Output is correct
6 Correct 273 ms 1272 KB Output is correct
7 Correct 249 ms 888 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 655 ms 51960 KB Output is correct
12 Correct 673 ms 51860 KB Output is correct
13 Correct 661 ms 52088 KB Output is correct
14 Correct 656 ms 52344 KB Output is correct
15 Correct 645 ms 52280 KB Output is correct
16 Correct 681 ms 51832 KB Output is correct
17 Correct 652 ms 51704 KB Output is correct
18 Correct 674 ms 51872 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 582 ms 52216 KB Output is correct
2 Correct 181 ms 1276 KB Output is correct
3 Correct 175 ms 1404 KB Output is correct
4 Correct 167 ms 1272 KB Output is correct
5 Correct 180 ms 1272 KB Output is correct
6 Correct 181 ms 1528 KB Output is correct
7 Correct 191 ms 1272 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 661 ms 51960 KB Output is correct
12 Correct 607 ms 52344 KB Output is correct
13 Correct 718 ms 52092 KB Output is correct
14 Correct 723 ms 52088 KB Output is correct
15 Correct 582 ms 52556 KB Output is correct
16 Correct 678 ms 52984 KB Output is correct
17 Correct 702 ms 53072 KB Output is correct
18 Correct 708 ms 53264 KB Output is correct
19 Correct 642 ms 52480 KB Output is correct
20 Correct 644 ms 52328 KB Output is correct
21 Correct 732 ms 52688 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1245 ms 54776 KB Output is correct
2 Correct 297 ms 1912 KB Output is correct
3 Correct 306 ms 1784 KB Output is correct
4 Correct 310 ms 1784 KB Output is correct
5 Correct 299 ms 1784 KB Output is correct
6 Correct 319 ms 1816 KB Output is correct
7 Correct 301 ms 1784 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1214 ms 53588 KB Output is correct
12 Correct 1149 ms 53496 KB Output is correct
13 Correct 1147 ms 53640 KB Output is correct
14 Correct 1206 ms 53880 KB Output is correct
15 Correct 1116 ms 53624 KB Output is correct
16 Correct 1198 ms 53736 KB Output is correct
17 Correct 1191 ms 53672 KB Output is correct
18 Correct 1161 ms 53660 KB Output is correct
19 Correct 1136 ms 53708 KB Output is correct
20 Correct 1151 ms 53496 KB Output is correct
21 Correct 1144 ms 53496 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 582 ms 52216 KB Output is correct
2 Correct 181 ms 1276 KB Output is correct
3 Correct 175 ms 1404 KB Output is correct
4 Correct 167 ms 1272 KB Output is correct
5 Correct 180 ms 1272 KB Output is correct
6 Correct 181 ms 1528 KB Output is correct
7 Correct 191 ms 1272 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 661 ms 51960 KB Output is correct
12 Correct 607 ms 52344 KB Output is correct
13 Correct 718 ms 52092 KB Output is correct
14 Correct 723 ms 52088 KB Output is correct
15 Correct 582 ms 52556 KB Output is correct
16 Correct 678 ms 52984 KB Output is correct
17 Correct 702 ms 53072 KB Output is correct
18 Correct 708 ms 53264 KB Output is correct
19 Correct 642 ms 52480 KB Output is correct
20 Correct 644 ms 52328 KB Output is correct
21 Correct 732 ms 52688 KB Output is correct
22 Incorrect 1226 ms 55120 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 677 ms 51964 KB Output is correct
2 Correct 256 ms 888 KB Output is correct
3 Correct 249 ms 888 KB Output is correct
4 Correct 262 ms 888 KB Output is correct
5 Correct 251 ms 992 KB Output is correct
6 Correct 273 ms 1272 KB Output is correct
7 Correct 249 ms 888 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 655 ms 51960 KB Output is correct
12 Correct 673 ms 51860 KB Output is correct
13 Correct 661 ms 52088 KB Output is correct
14 Correct 656 ms 52344 KB Output is correct
15 Correct 645 ms 52280 KB Output is correct
16 Correct 681 ms 51832 KB Output is correct
17 Correct 652 ms 51704 KB Output is correct
18 Correct 674 ms 51872 KB Output is correct
19 Incorrect 3 ms 384 KB Output isn't correct
20 Halted 0 ms 0 KB -