| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 634190 |
2022-08-24T05:03:32 Z |
S2speed |
ZIGZAG (INOI20_zigzag) |
C++17 |
|
762 ms |
90500 KB |
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define sze(x) (ll)(x.size())
typedef long long ll;
const ll maxn = 3e5 + 17;
struct node {
ll ans , p0 , p1 , s0 , s1 , l , fr , ls;
void def(){
ans = p0 = p1 = s0 = s1 = l = 0;
return;
}
void init(ll x){
ans = l = p0 = p1 = s0 = s1 = 1;
fr = ls = x;
return;
}
friend node operator + (node a , node b){
node res;
if(a.l == 0) return b;
if(b.l == 0) return a;
res.l = a.l + b.l;
res.fr = a.fr; res.ls = b.ls;
res.ans = a.ans + b.ans;
if(a.ls < b.fr){
res.ans += a.s0 * b.p1;
}
if(a.ls > b.fr){
res.ans += a.s1 * b.p0;
}
if(b.l & 1){
if(b.s0 == b.l && a.ls > b.fr){
res.s0 = b.l + a.s1;
} else {
res.s0 = b.s0;
}
if(b.s1 == b.l && a.ls < b.fr){
res.s1 = b.l + a.s0;
} else {
res.s1 = b.s1;
}
} else {
if(b.s0 == b.l && a.ls < b.fr){
res.s0 = b.l + a.s0;
} else {
res.s0 = b.s0;
}
if(b.s1 == b.l && a.ls > b.fr){
res.s1 = b.l + a.s1;
} else {
res.s1 = b.s1;
}
}
if(a.l & 1){
if(a.p0 == a.l && b.fr > a.ls){
res.p0 = a.l + b.p1;
} else {
res.p0 = a.p0;
}
if(a.p1 == a.l && b.fr < a.ls){
res.p1 = a.l + b.p0;
} else {
res.p1 = a.p1;
}
} else {
if(a.p0 == a.l && b.fr < a.ls){
res.p0 = a.l + b.p0;
} else {
res.p0 = a.p0;
}
if(a.p1 == a.l && b.fr > a.ls){
res.p1 = a.l + b.p1;
} else {
res.p1 = a.p1;
}
}
if(res.p0 == res.l) res.ans = res.l * (res.l + 1) / 2;
return res;
}
void rev(){
swap(p0 , p1); swap(s0 , s1);
ls = -ls; fr = -fr;
return;
}
friend void operator += (node &a , ll k){
a.ls += k; a.fr += k;
return;
}
};
struct segtree {
ll sz = 1;
vector<node> val;
vector<ll> laz , raz;
node def;
void init(ll n){
while(sz < n) sz <<= 1;
def.def();
val.assign(sz << 1 , def);
laz.assign(sz << 1 , 0); raz.assign(sz << 1 , 0);
return;
}
void build(vector<ll> &a , ll x , ll lx , ll rx){
if(rx - lx == 1){
if(lx < sze(a)){
val[x].init(a[lx]);
}
return;
}
ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
build(a , ln , lx , m); build(a , rn , m , rx);
val[x] = val[ln] + val[rn];
return;
}
void build(vector<ll> &a){
build(a , 0 , 0 , sz);
return;
}
void shift(ll x , ll lx , ll rx){
ll h = laz[x] , c = raz[x];
laz[x] = raz[x] = 0;
val[x] += h;
if(c) val[x].rev();
if(rx - lx == 1) return;
ll ln = (x << 1) + 1 , rn = ln + 1;
raz[ln] ^= c; raz[rn] ^= c;
if(raz[ln]) laz[ln] -= h;
else laz[ln] += h;
if(raz[rn]) laz[rn] -= h;
else raz[rn] += h;
return;
}
void add(ll l , ll r , ll k , ll x , ll lx , ll rx){
shift(x , lx , rx);
if(rx <= l || lx >= r) return;
if(rx <= r && lx >= l){
laz[x] = k;
shift(x , lx , rx);
return;
}
ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
add(l , r , k , ln , lx , m); add(l , r , k , rn , m , rx);
val[x] = val[ln] + val[rn];
return;
}
void add(ll l , ll r , ll k){
add(l , r , k , 0 , 0 , sz);
return;
}
void rev(ll l , ll r , ll x , ll lx , ll rx){
shift(x , lx , rx);
if(rx <= l || lx >= r) return;
if(rx <= r && lx >= l){
raz[x] = 1;
shift(x , lx , rx);
return;
}
ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
rev(l , r , ln , lx , m); rev(l , r , rn , m , rx);
val[x] = val[ln] + val[rn];
return;
}
void rev(ll l , ll r){
rev(l , r , 0 , 0 , sz);
return;
}
node cal(ll l , ll r , ll x , ll lx , ll rx){
shift(x , lx , rx);
if(rx <= l || lx >= r) return def;
if(rx <= r && lx >= l) return val[x];
ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
node a = cal(l , r , ln , lx , m) , b = cal(l , r , rn , m , rx);
return a + b;
}
ll cal(ll l , ll r){
node h = cal(l , r , 0 , 0 , sz);
return h.ans;
}
};
segtree st;
vector<ll> a;
int main(){
ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);
ll n , q;
cin>>n>>q;
st.init(n); a.resize(n);
for(ll i = 0 ; i < n ; i++){
cin>>a[i];
}
st.build(a);
for(ll e = 0 ; e < q ; e++){
char c;
ll l , r;
cin>>c>>l>>r; l--;
if(c == '*'){
st.rev(l , r);
} else if(c == '+'){
ll k;
cin>>k;
st.add(l , r , k);
} else {
cout<<st.cal(l , r)<<'\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
1748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
762 ms |
90500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
1748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
1748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
