oj.uz

Submission #284261

# Submission time Handle Problem Language Result Execution time Memory
284261 2020-08-27T06:01:48 Z 송준혁(#5749) Progression (NOI20_progression) C++17
44 / 100
 1264 ms 55192 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, l-1);
			upd(1, 1, N, l, l, s-x);
			x = sumq(1, 1, N, 1, r+1);
			upd(1, 1, N, r+1, r+1, x-(s+c*(r-l)));
			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 723 ms 54264 KB Output is correct
2 Correct 274 ms 3448 KB Output is correct
3 Correct 274 ms 3552 KB Output is correct
4 Correct 252 ms 3448 KB Output is correct
5 Correct 276 ms 3704 KB Output is correct
6 Correct 248 ms 3704 KB Output is correct
7 Correct 249 ms 3704 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 675 ms 54760 KB Output is correct
12 Correct 653 ms 54648 KB Output is correct
13 Correct 669 ms 55076 KB Output is correct
14 Correct 674 ms 54780 KB Output is correct
15 Correct 761 ms 54856 KB Output is correct
16 Correct 737 ms 54560 KB Output is correct
17 Correct 657 ms 54540 KB Output is correct
18 Correct 694 ms 54428 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 585 ms 54972 KB Output is correct
2 Correct 191 ms 3064 KB Output is correct
3 Correct 185 ms 3064 KB Output is correct
4 Correct 165 ms 3064 KB Output is correct
5 Correct 202 ms 3192 KB Output is correct
6 Correct 185 ms 3340 KB Output is correct
7 Correct 182 ms 3192 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 699 ms 54648 KB Output is correct
12 Correct 597 ms 54832 KB Output is correct
13 Correct 693 ms 54488 KB Output is correct
14 Correct 682 ms 54492 KB Output is correct
15 Correct 602 ms 54720 KB Output is correct
16 Correct 657 ms 55120 KB Output is correct
17 Correct 706 ms 55072 KB Output is correct
18 Correct 747 ms 55192 KB Output is correct
19 Correct 658 ms 54392 KB Output is correct
20 Correct 627 ms 54520 KB Output is correct
21 Correct 643 ms 54264 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 54972 KB Output is correct
2 Correct 191 ms 3064 KB Output is correct
3 Correct 185 ms 3064 KB Output is correct
4 Correct 165 ms 3064 KB Output is correct
5 Correct 202 ms 3192 KB Output is correct
6 Correct 185 ms 3340 KB Output is correct
7 Correct 182 ms 3192 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 699 ms 54648 KB Output is correct
12 Correct 597 ms 54832 KB Output is correct
13 Correct 693 ms 54488 KB Output is correct
14 Correct 682 ms 54492 KB Output is correct
15 Correct 602 ms 54720 KB Output is correct
16 Correct 657 ms 55120 KB Output is correct
17 Correct 706 ms 55072 KB Output is correct
18 Correct 747 ms 55192 KB Output is correct
19 Correct 658 ms 54392 KB Output is correct
20 Correct 627 ms 54520 KB Output is correct
21 Correct 643 ms 54264 KB Output is correct
22 Incorrect 1264 ms 53752 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 723 ms 54264 KB Output is correct
2 Correct 274 ms 3448 KB Output is correct
3 Correct 274 ms 3552 KB Output is correct
4 Correct 252 ms 3448 KB Output is correct
5 Correct 276 ms 3704 KB Output is correct
6 Correct 248 ms 3704 KB Output is correct
7 Correct 249 ms 3704 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 675 ms 54760 KB Output is correct
12 Correct 653 ms 54648 KB Output is correct
13 Correct 669 ms 55076 KB Output is correct
14 Correct 674 ms 54780 KB Output is correct
15 Correct 761 ms 54856 KB Output is correct
16 Correct 737 ms 54560 KB Output is correct
17 Correct 657 ms 54540 KB Output is correct
18 Correct 694 ms 54428 KB Output is correct
19 Incorrect 3 ms 384 KB Output isn't correct
20 Halted 0 ms 0 KB -