oj.uz

답안 #494673

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
494673 2021-12-16T01:46:00 Z jiahng Progression (NOI20_progression) C++14
57 / 100
 1427 ms 91096 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
typedef pair<int,int> pi;
typedef vector <ll> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(int i=s;i>=ll(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0)
#define MOD 1000000007
#define maxn 300010
#define data data1


struct data{
	int llen, rlen, lval, rval, sz, val;
	__int128 sm;
	data(int _sz, int _val, int _llen, int _rlen, int _lval, int _rval, __int128 _sm){
		llen = _llen; val = _val; rlen = _rlen, lval = _lval, rval = _rval; sz = _sz;
		sm = _sm;
	}
};

data merge(data x, data y){
	 int lval = x.lval, rval = y.rval;
	 int llen, rlen;
	 if (x.llen == x.sz && x.rval == y.lval) llen = x.llen + y.llen;
	 else llen = x.llen;
	 
	 if (y.rlen == y.sz && y.lval == x.rval) rlen = y.rlen + x.rlen;
	 else rlen = y.rlen;
	 
	 int val = max(x.val, y.val);
	 if (x.rval == y.lval) val = max(val, x.rlen + y.llen);
	 
	 return data(x.sz + y.sz, val, llen, rlen, lval, rval, x.sm + y.sm);
}
int N,Q;
int A[maxn],B[maxn];
struct node{
	int s,e,m,lazyadd=0,lazyset=0;
	bool lazyset_flag = 0;
	data dat = data(0,0,0,0,0,0,0);
	node *l,*r;
	node (int ss,int ee){
		s = ss; e = ee; m = (s + e) / 2;
		if (s == e){
			dat = data(1, 1, 1, 1, B[s], B[s],B[s]);
		}else{
			l = new node(s,m); r = new node(m+1,e);
			dat = merge(l->dat, r->dat);
		}
	}

	void prop(){
		if (lazyadd != 0){
			dat.lval += lazyadd; dat.rval += lazyadd; dat.sm += lazyadd * (e-s+1);
		}
		if (lazyset_flag){
			dat = data(e-s+1,e-s+1,e-s+1,e-s+1,lazyset,lazyset,(e-s+1)*lazyset);
		}
		
		
		if (s != e){
			if (lazyset_flag){
				l->lazyset_flag = r->lazyset_flag = 1;
				l->lazyadd = r->lazyadd = 0;
				l->lazyset = r->lazyset = lazyset;
			}
			if (lazyadd != 0){
				if (l->lazyset_flag) l->lazyset += lazyadd;
				else l->lazyadd += lazyadd;
				
				if (r->lazyset_flag) r->lazyset += lazyadd;
				else r->lazyadd += lazyadd;
			}
		}
				
		lazyadd = 0; lazyset_flag = 0; lazyset = 0;
	}
	void set(int a,int b,int c){
		prop();
		if (a <= s && e <= b){
			lazyset_flag = 1; lazyset = c; lazyadd = 0;
			prop();
		}else if (a > e || s > b) return;
		else{
			l->set(a,b,c); r->set(a,b,c);
			l->prop(); r->prop();
			dat = merge(l->dat, r->dat);
		}
	}
	void add(int a,int b,int c){
		prop();
		if (a <= s && e <= b){
			if (lazyset_flag) lazyset += c;
			else lazyadd += c;
			prop();
		}else if (a > e || s > b) return;
		else{
			l->add(a,b,c); r->add(a,b,c);
			l->prop(); r->prop();
			dat = merge(l->dat, r->dat);
		}
	}
	
	int qry(int a,int b){ // Largest contiguous equal sequence
		if (a > b) return 0;
		if (a == b) return 1;
		prop();
		if (a <= s && e <= b) return dat.val;
		else if (a > e || s > b) return 0;
		else{
			l->prop(); r->prop();
			int res = max(l->qry(a,b), r->qry(a,b));
			l->prop(); r->prop();
			if (l->dat.rval == r->dat.lval){
				int x = l->e - l->dat.rlen + 1;
				int y = r->s + r->dat.llen - 1;
				x = max(x, a); y = min(y, b);
				res = max(res, y - x + 1);;
			}
			return res;
		}
	}
	__int128 sum(int a,int b){
		prop();
		if (a <= s && e <= b) return dat.sm;
		else if (a > e || s > b) return 0;
		else return l->sum(a,b)+ r->sum(a,b);
	}
}*root;

int qryA(int p){
	//~ return A[p];
	if (p == 1) return A[1];
	else return ll(A[1] + root->sum(1, p-1));
}

int32_t main(){
    fast;
    cin >> N >> Q;
    FOR(i,1,N) cin >> A[i];
    FOR(i,1,N-1) B[i] = A[i+1] - A[i];
    if (N > 1) root = new node(1,N-1);

    int t,l,r,s,c;
    FOR(q,1,Q){
		cin >> t;
		if (t == 1){ // add
			cin >> l >> r >> s >> c;
			if (N == 1) continue;
			
			if (l > 1){
				root->add(l-1,l-1,s);
				//~ cout << "ADD " << l-1 << ' ' << l-1 << ' ' << s << '\n';
			}
			if (r < N){
				root->add(r,r,-(s+(r-l)*c));
				//~ cout << "ADD " << r << ' ' << r << ' ' << -(s+(r-l)*c) << '\n';
			}
			if (l < r) root->add(l,r-1,c);
			//~ cout << "ADD " << l << ' ' << r-1 << ' ' << c << '\n';
			//~ FOR(i,l,r) A[i] += s + (i-l)*c;
			if (l == 1) A[1] += s;
		}else if (t == 2){ //set
			cin >> l >> r >> s >> c;
			if (N == 1) continue;
			//~ FOR(i,l,r) A[i] = s + (i-l)*c;
			
			if (l > 1) root->set(l-1,l-1,s-qryA(l-1));
			if (r < N) root->set(r,r,qryA(r+1)-(s+(r-l)*c));
			if (l < r) root->set(l,r-1,c);
			if (l == 1) A[1] = s;
		}else{
			cin >> l >> r;
			if (N == 1 || l == r) cout << 1 << '\n';
			else cout << root->qry(l,r-1) + 1 << '\n';
		}
	}
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 161 ms 90128 KB Output is correct
2 Correct 76 ms 568 KB Output is correct
3 Correct 74 ms 552 KB Output is correct
4 Correct 80 ms 572 KB Output is correct
5 Correct 74 ms 580 KB Output is correct
6 Correct 75 ms 672 KB Output is correct
7 Correct 76 ms 628 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 168 ms 90136 KB Output is correct
12 Correct 164 ms 90024 KB Output is correct
13 Correct 175 ms 90364 KB Output is correct
14 Correct 180 ms 90340 KB Output is correct
15 Correct 161 ms 90316 KB Output is correct
16 Correct 171 ms 89988 KB Output is correct
17 Correct 171 ms 90044 KB Output is correct
18 Correct 177 ms 90040 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 420 ms 90484 KB Output is correct
2 Correct 96 ms 924 KB Output is correct
3 Correct 83 ms 884 KB Output is correct
4 Correct 67 ms 920 KB Output is correct
5 Correct 91 ms 964 KB Output is correct
6 Correct 91 ms 896 KB Output is correct
7 Correct 89 ms 972 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 449 ms 90308 KB Output is correct
12 Correct 410 ms 90564 KB Output is correct
13 Correct 468 ms 90348 KB Output is correct
14 Correct 490 ms 90308 KB Output is correct
15 Correct 421 ms 90564 KB Output is correct
16 Correct 469 ms 90812 KB Output is correct
17 Correct 455 ms 90820 KB Output is correct
18 Correct 502 ms 91096 KB Output is correct
19 Correct 446 ms 90172 KB Output is correct
20 Correct 405 ms 90220 KB Output is correct
21 Correct 450 ms 90180 KB Output is correct

Subtask #4
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 890 ms 89904 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 420 ms 90484 KB Output is correct
2 Correct 96 ms 924 KB Output is correct
3 Correct 83 ms 884 KB Output is correct
4 Correct 67 ms 920 KB Output is correct
5 Correct 91 ms 964 KB Output is correct
6 Correct 91 ms 896 KB Output is correct
7 Correct 89 ms 972 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 449 ms 90308 KB Output is correct
12 Correct 410 ms 90564 KB Output is correct
13 Correct 468 ms 90348 KB Output is correct
14 Correct 490 ms 90308 KB Output is correct
15 Correct 421 ms 90564 KB Output is correct
16 Correct 469 ms 90812 KB Output is correct
17 Correct 455 ms 90820 KB Output is correct
18 Correct 502 ms 91096 KB Output is correct
19 Correct 446 ms 90172 KB Output is correct
20 Correct 405 ms 90220 KB Output is correct
21 Correct 450 ms 90180 KB Output is correct
22 Correct 1324 ms 89924 KB Output is correct
23 Correct 160 ms 544 KB Output is correct
24 Correct 162 ms 752 KB Output is correct
25 Correct 156 ms 532 KB Output is correct
26 Correct 163 ms 492 KB Output is correct
27 Correct 181 ms 644 KB Output is correct
28 Correct 160 ms 560 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 1 ms 204 KB Output is correct
32 Correct 1427 ms 89928 KB Output is correct
33 Correct 1323 ms 89924 KB Output is correct
34 Correct 1353 ms 89960 KB Output is correct
35 Correct 1297 ms 89968 KB Output is correct
36 Correct 1020 ms 90172 KB Output is correct
37 Correct 988 ms 90176 KB Output is correct
38 Correct 936 ms 90196 KB Output is correct
39 Correct 1278 ms 90144 KB Output is correct
40 Correct 1320 ms 89924 KB Output is correct
41 Correct 1380 ms 90080 KB Output is correct
42 Correct 1343 ms 89996 KB Output is correct
43 Correct 1313 ms 89816 KB Output is correct
44 Correct 1342 ms 90008 KB Output is correct
45 Correct 1244 ms 89924 KB Output is correct

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 161 ms 90128 KB Output is correct
2 Correct 76 ms 568 KB Output is correct
3 Correct 74 ms 552 KB Output is correct
4 Correct 80 ms 572 KB Output is correct
5 Correct 74 ms 580 KB Output is correct
6 Correct 75 ms 672 KB Output is correct
7 Correct 76 ms 628 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 168 ms 90136 KB Output is correct
12 Correct 164 ms 90024 KB Output is correct
13 Correct 175 ms 90364 KB Output is correct
14 Correct 180 ms 90340 KB Output is correct
15 Correct 161 ms 90316 KB Output is correct
16 Correct 171 ms 89988 KB Output is correct
17 Correct 171 ms 90044 KB Output is correct
18 Correct 177 ms 90040 KB Output is correct
19 Incorrect 2 ms 588 KB Output isn't correct
20 Halted 0 ms 0 KB -