| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 623630 |
2022-08-06T07:12:54 Z |
Arinoor |
ZIGZAG (INOI20_zigzag) |
C++17 |
|
845 ms |
84296 KB |
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mid ((l + r) >> 1)
#define lc (id << 1)
#define rc (lc | 1)
#define all(x) x.begin(), x.end()
#define bug(x) cout << #x << " : " << x << '\n'
#define ios ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 3e5 + 10;
const int mod = 1e9 + 7;
const int inf = 1e9 + 10;
struct node{
ll ans;
int L, R;
ll l1, l2, r1, r2;
int len;
};
node operator + (node l, node r){
if(l.ans == -1) return r;
if(r.ans == -1) return l;
node S;
S.len = l.len + r.len;
S.l1 = l.l1, S.r1 = r.r1;
if(l.len > 1)
S.l2 = l.l2;
else
S.l2 = r.l1;
if(r.len > 1)
S.r2 = r.r2;
else
S.r2 = l.r1;
S.L = l.L;
if(l.L == l.len){
if(l.r1 != r.l1 and (l.len == 1 or (l.r2 < l.r1) != (l.r1 < r.l1))){
S.L ++;
if(r.len == 1 or (l.r1 < r.l1) != (r.l1 < r.l2)){
S.L = l.L + r.L;
}
}
}
S.R = r.R;
if(r.R == r.len){
if(r.l1 != l.r1 and (r.len == 1 or (l.r1 < r.l1) != (r.l1 < r.l2))){
S.R ++;
if(l.len == 1 or (l.r2 < l.r1) != (l.r1 < r.l1)){
S.R = r.R + l.R;
}
}
}
S.ans = l.ans + r.ans;
if(l.r1 != r.l1){
int valL = 1, valR = 1;
if(r.len == 1 or (l.r1 < r.l1) != (r.l1 < r.l2))
valR = r.L;
if(l.len == 1 or (l.r2 < l.r1) != (l.r1 < r.l1))
valL = l.R;
S.ans += 1ll * valL * valR;
}
return S;
}
int a[maxn];
pair<int, ll> lz[maxn << 2];
node seg[maxn << 2];
void build(int id, int l, int r){
seg[id].ans = seg[id].len = r - l;
seg[id].L = seg[id].R = 1;
lz[id] = mp(1, 0);
if(l + 1 == r)
return;
build(lc, l, mid);
build(rc, mid, r);
}
void shift(int id, int l, int r);
void update(int id, int l, int r, int ql, int qr, bool t, int x){
if(qr <= l or r <= ql)
return;
if(l >= ql and r <= qr){
if(t){
seg[id].l1 *= -1;
seg[id].r1 *= -1;
if(seg[id].len > 1){
seg[id].l2 *= -1;
seg[id].r2 *= -1;
}
lz[id].fi *= -1;
lz[id].se *= -1;
}
else{
seg[id].l1 += x;
seg[id].r1 += x;
if(seg[id].len > 1){
seg[id].l2 += x;
seg[id].r2 += x;
}
lz[id].se += x;
}
return;
}
shift(id, l, r);
update(lc, l, mid, ql, qr, t, x);
update(rc, mid, r, ql, qr, t, x);
seg[id] = seg[lc] + seg[rc];
}
void shift(int id, int l, int r){
if(lz[id].fi == -1){
update(lc, l, mid, l, mid, 1, -1);
update(rc, mid, r, mid, r, 1, -1);
lz[id].fi = 1;
}
if(lz[id].se){
update(lc, l, mid, l, mid, 0, lz[id].se);
update(rc, mid, r, mid, r, 0, lz[id].se);
lz[id].se = 0;
}
}
node get(int id, int l, int r, int ql, int qr){
if(qr <= l or r <= ql)
return node{-1, -1, -1, -1, -1, -1, -1};
if(l >= ql and r <= qr)
return seg[id];
shift(id, l, r);
node L = get(lc, l, mid, ql, qr);
node R = get(rc, mid, r, ql, qr);
if(id == -1){
bug(L.ans), bug(L.L), bug(L.R), bug(L.l1), bug(L.l2), bug(L.r1), bug(L.r2), bug(L.len);
bug(R.ans), bug(R.L), bug(R.R), bug(R.l1), bug(R.l2), bug(R.r1), bug(R.r2), bug(R.len);
}
return L + R;
}
int main(){
ios;
int n, q;
cin >> n >> q;
build(1, 0, n);
for(int i = 0; i < n; i ++){
cin >> a[i];
update(1, 0, n, i, i + 1, 0, a[i]);
}
while(q--){
char c;
int l, r;
cin >> c >> l >> r;
l --;
if(c == '+'){
int x; cin >> x;
update(1, 0, n, l, r, 0, x);
}
if(c == '*'){
update(1, 0, n, l, r, 1, -1);
}
if(c == '?'){
cout << get(1, 0, n, l, r).ans << '\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
1620 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
1624 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
845 ms |
81080 KB |
Output is correct |
| 2 |
Correct |
52 ms |
2436 KB |
Output is correct |
| 3 |
Incorrect |
716 ms |
84296 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
1620 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
1624 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
1620 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
1624 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
