Submission #583418

#	Time	Username	Problem	Language	Result	Execution time	Memory
583418		lukameladze	ZIGZAG (INOI20_zigzag)	C++14	8 / 100	2076 ms	7932 KiB

Main

# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair <int, int>
#define pb push_back
const int N = 3e5 + 5;
int tree[4*N],dp[N],n;
long long a[N];
void build(int node, int le, int ri/* int type 0-even,1-odd*/) {
    if (le == ri) {
        tree[node] = dp[le];
        return ;
    }
    int mid = (le + ri) / 2;
    build(2*node,le,mid);
    build(2*node + 1, mid + 1, ri);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}
void update(int node, int le, int ri, int idx, int val) {
    if (le > idx || ri < idx) return ;
    if (le == ri) {
        tree[node] = val;
        return ;
    }
    int mid = (le + ri) / 2;
    update(2*node,le,mid,idx,val);
    update(2*node + 1, mid + 1, ri, idx, val);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}
int getans(int node, int le, int ri, int start, int end) {
    if (start > end) return 0;
    if (le > end || ri < start) return 0;
    if (le >= start && ri <= end) return tree[node];
    int mid = (le + ri) / 2;
    return getans(2*node,le,mid,start,end) + getans(2*node + 1, mid + 1, ri, start, end);
}
void upd(int idx) {
    if (idx == n) {
        dp[idx] = n;
        return ;
    }
    if (a[idx] == a[idx + 1]) dp[idx] = idx;
        else dp[idx] = idx + 1;
    if (idx < n - 1) {
        if ((a[idx] < a[idx + 1] && a[idx + 1] > a[idx + 2]) || (a[idx] > a[idx + 1] && a[idx + 1] < a[idx + 2]))
        dp[idx] = dp[idx + 1];
    }
    return ;
}
/*
void prnt() {
    for (int i = 1; i <= n; i++) {
        cout<<dp[i]<<" ";
    }
    cout<<"\n";
    cout<<"\n";
}*/
void go(int l, int r, int val, int type) {
    int prer = a[r];
    int changed = 0;
    int to = 0;
    int prel = a[l];
   // prnt();
    if (type == 0) {
        for (int i = l; i <= r; i++) {
            a[i] += val;
        }    
    }
    if (type == 1) {
        for (int i = l; i <= r; i++) {
            a[i] *= -1;
        }
    }
    int curl = a[l];
    int curr = a[r];
    int ff = 0;
    if (r < n) {
        if (prer > a[r + 1] && curr < a[r + 1]) changed = 1;
        if (prer == a[r + 1] && curr != a[r + 1]) changed = 1;
        if (prer != a[r + 1] && curr == a[r + 1]) changed = 1;
        if (prer < a[r + 1] && curr > a[r + 1]) changed = 1;
    }
    if (true) {
        upd(r);
        update(1,1,n,r,dp[r]);
        for (int i = r - 1; i >= 1; i--) {
            upd(i);
            update(1,1,n,i,dp[i]);
        }
    }
    changed = 0;
    
    if (l > 1) {
        if (prel > a[l - 1] && curl < a[l - 1]) changed = 1;
        if (prel == a[l - 1] && curl != a[l - 1]) changed = 1;
        if (prel != a[l - 1] && curl == a[l - 1]) changed = 1;
        if (prel < a[l - 1] && curl > a[l - 1]) changed = 1;
    }
    //cout<<changed<<"\n";
    if (true) {
        int to = getans(1,1,n,l,l);
        upd(l);
        upd(l - 1);
        update(1,1,n, l - 1, dp[l - 1]);
        for (int i = l - 2; i >= 1; i--) {
            upd(i);
            update(1,1,n,i,dp[i]);
        }
    }
   // prnt();
}
int get(int x) {
    return (x*(x + 1)) / 2;
}
int getpas(int l, int r) {
    int le = l;
    int ri = r;
    int pas = -1;
   
    while (le <= ri) {
        int mid = (le + ri) / 2;
        if (getans(1,1,n,mid,mid) > r) {
            ri = mid - 1;
            pas = mid;
        } else le = mid + 1;
    }
    int startsum = get(r) - get(l - 1);
    int endsum = 0;
    if (pas == -1) {
        endsum = getans(1,1,n,l,r) + (r - l + 1);
    } else {
        endsum = getans(1,1,n,l,pas - 1) + (r - pas + 1)*r + (r - l + 1);
    }
    return endsum - startsum;
}
signed main() {
    std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int q;
    cin>>n>>q;
    for (int i = 1; i <= n; i++) {
        cin>>a[i];
    }
    dp[n] = n;
    upd(n);
    upd(n - 1);
    for (int i = n - 2; i >= 1; i--) {
       upd(i);
    }
    build(1,1,n);
    
    while (q--) {
        char ch;
        cin>>ch;
        if (ch == '+') {
            int l,r,val;
            cin>>l>>r>>val;
            go(l,r,val,0);
            continue;
        }
        if (ch == '*') {
            int l,r;
            cin>>l>>r;
            go(l,r,0,1);
            continue;
        }
        if (ch == '?') {
            int l,r;
            cin>>l>>r;
            cout<<getpas(l,r)<<endl;
            continue;
        }
    }
}

Compilation message (stderr)

Main.cpp: In function 'void go(int, int, int, int)':
Main.cpp:102:13: warning: unused variable 'to' [-Wunused-variable]
  102 |         int to = getans(1,1,n,l,l);
      |             ^~
Main.cpp:61:9: warning: variable 'changed' set but not used [-Wunused-but-set-variable]
   61 |     int changed = 0;
      |         ^~~~~~~
Main.cpp:62:9: warning: unused variable 'to' [-Wunused-variable]
   62 |     int to = 0;
      |         ^~
Main.cpp:77:9: warning: unused variable 'ff' [-Wunused-variable]
   77 |     int ff = 0;
      |         ^~

• Subtask 1: 8 / 8
• Subtask 2: 0 / 42
• Subtask 3: 0 / 35
• Subtask 4: 0 / 15