oj.uz

Submission #593003

# Submission time Handle Problem Language Result Execution time Memory
593003 2022-07-10T06:11:18 Z radal ZIGZAG (INOI20_zigzag) C++17
100 / 100
 903 ms 80516 KB 
#include <bits/stdc++.h>
//#pragma GCC target("sse,sse2")
//#pragma GCC optimize("unroll-loops,O3")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 3e5+5,mod = 1e9+7,inf = 1e9+10,base = 211;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
   // if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    } 
    return z; 
}
int n,za[N*4],a[N];
ll lz[N*4],seg[N*4][7]; // val l val r pre ^ pre ! suf ^ suf ! ans
inline void calc(int l,int r,int v){
    int u = (v << 1),m = (l+r) >> 1;
    seg[v][0] = seg[u][0];
    seg[v][1] = seg[u|1][1];
    seg[v][6] = seg[u][6]+seg[u|1][6];
    seg[v][2] = seg[u][2];
    seg[v][3] = seg[u][3];
    seg[v][4] = seg[u|1][4];
    seg[v][5] = seg[u|1][5];
    if (seg[u][1] == seg[u|1][0]) return;
    if (seg[u][1] < seg[u|1][0]){
        seg[v][6] += seg[u][5]*seg[u|1][3];
        if (seg[u][2] == m-l && ((m-l)&1))
            seg[v][2] += seg[u|1][3];
        if (seg[u][3] == m-l && ((m-l)&1) == 0)
            seg[v][3] += seg[u|1][3];
        if (seg[u|1][4] == r-m && ((r-m)&1))
            seg[v][4] += seg[u][5];
        if (seg[u|1][5] == r-m && ((r-m)&1) == 0)
            seg[v][5] += seg[u][5];
        return;
    }
    seg[v][6] += seg[u][4]*seg[u|1][2];
    if (seg[u][2] == m-l && ((m-l)&1) == 0)
        seg[v][2] += seg[u|1][2];
    if (seg[u][3] == m-l && ((m-l)&1))
        seg[v][3] += seg[u|1][2];
    if (seg[u|1][4] == r-m && ((r-m)&1) == 0)
        seg[v][4] += seg[u][4];
    if (seg[u|1][5] == r-m && ((r-m)&1))
        seg[v][5] += seg[u][4];
}
void build(int l,int r,int v = 1){
    za[v] = 1;
    if (r-l == 1){
        seg[v][0] = seg[v][1] = a[l];
        seg[v][2] = seg[v][3] = seg[v][4] = seg[v][5] = seg[v][6] = 1;
        return;
    }
    int m = (l+r) >> 1,u = (v << 1);
    build(l,m,u);
    build(m,r,u|1);
    calc(l,r,v);
}
inline void passza(int v){
    za[v] *= -1;
    lz[v] *= -1;
    seg[v][0] *= -1;
    seg[v][1] *= -1;
    swap(seg[v][2],seg[v][3]);
    swap(seg[v][4],seg[v][5]);
}
inline void passlz(int v){
    int u = (v << 1);
    lz[u] += lz[v];
    lz[u|1] += lz[v];
    seg[u][0] += lz[v];
    seg[u][1] += lz[v];
    seg[u|1][0] += lz[v];
    seg[u|1][1] += lz[v];
    lz[v] = 0;
}
void upd1(int l,int r,int s,int e,int v){
    if (s >= r || l >= e) return;
    if (s <= l && r <= e){
        passza(v);
        return;
    }
    int u = (v << 1),m = (l+r) >> 1;
    if(za[v] == -1){
        za[v] = 1;
        passza(u);
        passza(u|1);
    }
    if (lz[v])
        passlz(v);
    upd1(l,m,s,e,u);
    upd1(m,r,s,e,u|1);
    calc(l,r,v);
}
void upd2(int l,int r,int s,int e,int x,int v){
    if (s >= r || l >= e) return;
    if (s <= l && r <= e){
        lz[v] += x;
        seg[v][0] += x;
        seg[v][1] += x;
        return;
    }
    int u = (v << 1),m = (l+r) >> 1;
    if(za[v] == -1){
        za[v] = 1;
        passza(u);
        passza(u|1);
    }
    if (lz[v])
        passlz(v);
    upd2(l,m,s,e,x,u);
    upd2(m,r,s,e,x,u|1);
    calc(l,r,v);
}
vector<ll> que(int l,int r,int s,int e,int v = 1){
    vector<ll> ans;
    if (l == s && r == e){
        rep(i,0,7) ans.pb(seg[v][i]);
        return ans;
    }
    int u = (v << 1),m = (l+r) >> 1;
    if(za[v] == -1){
        za[v] = 1;
        passza(u);
        passza(u|1);
    }
    if (lz[v])
        passlz(v);
    if (e <= m) return que(l,m,s,e,u);
    if (s >= m) return que(m,r,s,e,u|1);
    vector<ll> v1,v2;
    v1 = que(l,m,s,m,u);
    v2 = que(m,r,m,e,u|1);
    ans.resize(7);
    ans[0] = v1[0];
    ans[1] = v2[1];
    ans[2] = v1[2];
    ans[3] = v1[3];
    ans[4] = v2[4];
    ans[5] = v2[5];
    ans[6] = v1[6]+v2[6];
    if (v1[1] == v2[0])
        return ans;
    if (v1[1] < v2[0]){
        ans[6] += v1[5]*v2[3];
        if (v1[2] == m-s && ((m-s)&1))
            ans[2] += v2[3];
        if (v1[3] == m-s && ((m-s)&1) == 0)
            ans[3] += v2[3];
        if (v2[4] == e-m && ((e-m)&1))
            ans[4] += v1[5];
        if (v2[5] == e-m && ((e-m)&1) == 0)
            ans[5] += v1[5];
        return ans;
    }
    ans[6] += v1[4]*v2[2];
    if (v1[2] == m-s && ((m-s)&1) == 0)
        ans[2] += v2[2];
    if (v1[3] == m-s && ((m-s)&1))
        ans[3] += v2[2];
    if (v2[4] == e-m && ((e-m)&1) == 0)
        ans[4] += v1[4];
    if (v2[5] == e-m && ((e-m)&1))
        ans[5] += v1[4];
    return ans;
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    int q;
    cin >> n >> q;
    rep(i,0,n) cin >>a[i];
    build(0,n,1);
    while (q--){
        char c;
        int l,r;
        cin >> c >> l >> r;
        l--;
        if (c == '*'){
            upd1(0,n,l,r,1);
            continue;
        }
        if (c == '+'){
            int x;
            cin >> x;
            upd2(0,n,l,r,x,1);
            continue;
        }
        vector<ll> ans = que(0,n,l,r,1);
        cout << ans[6] << endl;
    }
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1472 KB Output is correct
2 Correct 8 ms 1596 KB Output is correct
3 Correct 8 ms 1492 KB Output is correct
4 Correct 8 ms 1492 KB Output is correct
5 Correct 8 ms 1448 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 9 ms 1484 KB Output is correct

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 71960 KB Output is correct
2 Correct 65 ms 2636 KB Output is correct
3 Correct 369 ms 80160 KB Output is correct
4 Correct 515 ms 80188 KB Output is correct
5 Correct 413 ms 80212 KB Output is correct
6 Correct 437 ms 80092 KB Output is correct
7 Correct 471 ms 77168 KB Output is correct
8 Correct 463 ms 80096 KB Output is correct
9 Correct 421 ms 80132 KB Output is correct
10 Correct 319 ms 79948 KB Output is correct
11 Correct 413 ms 80496 KB Output is correct
12 Correct 460 ms 80184 KB Output is correct
13 Correct 246 ms 78156 KB Output is correct
14 Correct 236 ms 78020 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1472 KB Output is correct
2 Correct 8 ms 1596 KB Output is correct
3 Correct 8 ms 1492 KB Output is correct
4 Correct 8 ms 1492 KB Output is correct
5 Correct 8 ms 1448 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 9 ms 1484 KB Output is correct
8 Correct 257 ms 20056 KB Output is correct
9 Correct 223 ms 19976 KB Output is correct
10 Correct 251 ms 21040 KB Output is correct
11 Correct 228 ms 18652 KB Output is correct
12 Correct 233 ms 21068 KB Output is correct
13 Correct 227 ms 21120 KB Output is correct
14 Correct 217 ms 21072 KB Output is correct
15 Correct 217 ms 19964 KB Output is correct
16 Correct 232 ms 20996 KB Output is correct
17 Correct 227 ms 21084 KB Output is correct
18 Correct 71 ms 20516 KB Output is correct
19 Correct 72 ms 20452 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1472 KB Output is correct
2 Correct 8 ms 1596 KB Output is correct
3 Correct 8 ms 1492 KB Output is correct
4 Correct 8 ms 1492 KB Output is correct
5 Correct 8 ms 1448 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 9 ms 1484 KB Output is correct
8 Correct 438 ms 71960 KB Output is correct
9 Correct 65 ms 2636 KB Output is correct
10 Correct 369 ms 80160 KB Output is correct
11 Correct 515 ms 80188 KB Output is correct
12 Correct 413 ms 80212 KB Output is correct
13 Correct 437 ms 80092 KB Output is correct
14 Correct 471 ms 77168 KB Output is correct
15 Correct 463 ms 80096 KB Output is correct
16 Correct 421 ms 80132 KB Output is correct
17 Correct 319 ms 79948 KB Output is correct
18 Correct 413 ms 80496 KB Output is correct
19 Correct 460 ms 80184 KB Output is correct
20 Correct 246 ms 78156 KB Output is correct
21 Correct 236 ms 78020 KB Output is correct
22 Correct 257 ms 20056 KB Output is correct
23 Correct 223 ms 19976 KB Output is correct
24 Correct 251 ms 21040 KB Output is correct
25 Correct 228 ms 18652 KB Output is correct
26 Correct 233 ms 21068 KB Output is correct
27 Correct 227 ms 21120 KB Output is correct
28 Correct 217 ms 21072 KB Output is correct
29 Correct 217 ms 19964 KB Output is correct
30 Correct 232 ms 20996 KB Output is correct
31 Correct 227 ms 21084 KB Output is correct
32 Correct 71 ms 20516 KB Output is correct
33 Correct 72 ms 20452 KB Output is correct
34 Correct 0 ms 340 KB Output is correct
35 Correct 0 ms 340 KB Output is correct
36 Correct 889 ms 77492 KB Output is correct
37 Correct 896 ms 80312 KB Output is correct
38 Correct 722 ms 71288 KB Output is correct
39 Correct 832 ms 80476 KB Output is correct
40 Correct 878 ms 77412 KB Output is correct
41 Correct 815 ms 80368 KB Output is correct
42 Correct 776 ms 77560 KB Output is correct
43 Correct 903 ms 80468 KB Output is correct
44 Correct 849 ms 80360 KB Output is correct
45 Correct 835 ms 80344 KB Output is correct
46 Correct 785 ms 80516 KB Output is correct
47 Correct 763 ms 78540 KB Output is correct