oj.uz

Submission #583378

# Submission time Handle Problem Language Result Execution time Memory
583378 2022-06-25T10:02:49 Z GioChkhaidze ZIGZAG (INOI20_zigzag) C++14
8 / 100
 2000 ms 14244 KB 
#include <bits/stdc++.h>
 
#define lf (h << 1)
#define mf ((l + r) >> 1)
#define rf ((h << 1) | 1)
#define tree int h, int l, int r
#define left lf, l, mf
#define right rf, mf + 1, r
#define ll long long
#define int long long
 
using namespace std;
 
const int N = 3e5 + 5;

int n, m, q,  L, R, id, a[N];
ll vl, b[N], vd[4 * N];
bool dv[4 * N], tp;

struct node {
	ll ans;
	int pr;
	int sf;
	ll fr;
	ll ls;
	int len;
	bool add;
};
 
node v[4 * N], bs = {0, 0, 0, 0, 0, 0, 0};
 
node merge(node a, node b) {
	node c;
	c.add = 0;
	c.ans = a.ans + b.ans;
	c.fr = a.fr, c.ls = b.ls;
	c.sf = b.sf, c.pr = a.pr;
	if ((a.ls < 0 && b.fr > 0) || (a.ls > 0 && b.fr < 0)) {
		if (b.sf == b.len) c.sf += a.sf;
		if (a.pr == a.len) c.pr += b.pr;	
		c.ans += a.sf * b.pr;
	}
	return c;
}
 
void build(tree) {
	if (l == r) {
		v[h].len = 1;
		v[h].fr = b[l];
		v[h].ls = b[l];
		if (v[h].fr) {
			v[h].pr = v[h].sf = v[h].ans = 1;
		}
		return ;
	}
	build(left), build(right);
	v[h] = merge(v[lf], v[rf]);
	v[h].len = v[lf].len + v[rf].len;
}
 
void shift(tree) {
	if (v[h].add) {
		v[lf].add ^= 1, v[lf].fr *= -1; v[lf].ls *= -1;
		v[rf].add ^= 1, v[rf].fr *= -1; v[rf].ls *= -1;
		v[h].add = 0;
		return ;
	}
}
 
node get(tree) {
	if (r < L || R < l) return bs;
	if (L <= l && r <= R) return v[h];
	shift(h, l, r);
	return merge(get(left), get(right));
}
 
void upd(tree) {
	if (r < id || id < l) return ;
	if (l == id && id == r) {
		v[h].fr += vl; 
		v[h].ls += vl;
		if (v[h].fr) {
			v[h].pr = v[h].sf = v[h].ans = 1;
		}
			else {
			v[h].pr = v[h].sf = v[h].ans = 0;
		}
		return ;
	}
	shift(h, l, r);
	upd(left), upd(right);
	v[h] = merge(v[lf], v[rf]);
}
 
void upd_(tree) {
	if (r < L || R < l) return ;
	if (L <= l && r <= R) {
		v[h].add ^= 1;
		v[h].fr *= -1;
		v[h].ls *= -1;
		return ;
	}
	shift(h, l, r);
	upd_(left), upd_(right);
	v[h] = merge(v[lf], v[rf]);
}
 
void bld(tree) {
	if (l == r) { vd[h] = a[l]; return ; }
	bld(left); bld(right);
}
 
void shf(tree) {
	if (dv[h]) {
		vd[lf] = vd[lf] * -1 + vd[h];
		vd[rf] = vd[rf] * -1 + vd[h];
		dv[lf] ^= 1, dv[rf] ^= 1;
	}
		else {
		vd[lf] += vd[h];
		vd[rf] += vd[h];
	}
	vd[h] = dv[h] = 0;
	return ;
}
 
void up(tree) {
	if (r < L || R < l) return ;
	if (L <= l && r <= R) {
		if (tp == 0) {
			vd[h] += vl;
		}
			else
		if (tp == 1) {
			vd[h] *= -1;  
			dv[h] ^= 1;
		}
		return ;
	}
	shf(h, l, r);
	up(left), up(right);
} 
 
int G(tree) {
	if (l == r) return vd[h];
	shf(h, l, r);
	if (id <= mf) 
		return G(left);
	return G(right);
}
 
main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		if (1 < i) {
			b[i - 1] = a[i - 1] - a[i];
		}
	}
 
	//m = n - 1, build(1, 1, m);
	bld(1, 1, n);
	for (int i = 1; i <= q; ++i) {
		char c;
		cin >> c;
		if (c == '+') {
			cin >> L >> R >> vl; tp = 0, up(1, 1, n), --L;
			//vl = -vl, id = L; if (1 <= L) upd(1, 1, m);
			//vl = -vl, id = R; if (R <= m) upd(1, 1, m);
		}
			else
		if (c == '*') {
			vl = 0;
			cin >> L >> R; 
			if (1 < L) {
				id = L;
				ll Al = G(1, 1, n);
				id = L - 1;
				vl = 2 * Al;
				//upd(1, 1, m);
			}
			if (R < n) { 
				id = R;
				ll Ar = G(1, 1, n);
				vl = -2 * Ar;
				//upd(1, 1, m);
			}
			
			tp = 1, up(1, 1, n);
			//--R, upd_(1, 1, m);
		}
			else 
		if (c == '?') {
			cin >> L >> R; 
			
			for (int j = L; j <= R; ++j) {
				id = j, a[j] = G(1, 1, n);
			}

			--R;
			
			ll pas=1, XC = 0, ZX = 0;
            ll zx=1, xc=1;
            for(int i=R; i>=L; i--){
                if(a[i]==a[i+1]){
                    pas++;
                    zx=1;xc=1;
                    continue;
                }
                pas++;
                if(a[i]<a[i+1]){
                    pas+=xc;
                    ZX=xc+1;XC=1;
                    zx=ZX;xc=XC;
                }else{
                    pas+=zx;
                    ZX=1;XC=zx+1;
                    zx=ZX;xc=XC;
                }
            }
            cout<<pas<<"\n";

			//cout << get(1, 1, m).ans + R - L + 2 << "\n";
		}
	}
}

Compilation message

Main.cpp:152:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  152 | main() {
      | ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 568 KB Output is correct
2 Correct 209 ms 688 KB Output is correct
3 Correct 230 ms 564 KB Output is correct
4 Correct 270 ms 568 KB Output is correct
5 Correct 226 ms 572 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 806 ms 568 KB Output is correct

Subtask #2
0 / 42.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2069 ms 14244 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 568 KB Output is correct
2 Correct 209 ms 688 KB Output is correct
3 Correct 230 ms 564 KB Output is correct
4 Correct 270 ms 568 KB Output is correct
5 Correct 226 ms 572 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 806 ms 568 KB Output is correct
8 Execution timed out 2073 ms 4212 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 568 KB Output is correct
2 Correct 209 ms 688 KB Output is correct
3 Correct 230 ms 564 KB Output is correct
4 Correct 270 ms 568 KB Output is correct
5 Correct 226 ms 572 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 806 ms 568 KB Output is correct
8 Execution timed out 2069 ms 14244 KB Time limit exceeded
9 Halted 0 ms 0 KB -