Submission #583395

#	Time	Username	Problem	Language	Result	Execution time	Memory
583395		lukameladze	ZIGZAG (INOI20_zigzag)	C++14	0 / 100	2083 ms	7044 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],a[N],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 go(int l, int r, int val, int type) {
    int prer = a[r];
    int changed = 0;
    int to = 0;
    int prel = a[l];
    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 (changed) {
        if (r == n) dp[r] = r;
        else {
            if (a[r] == a[r + 1]) dp[r] = r;
            else dp[r] = r + 1;
        }
        if (r < n - 1) {
            if ((a[r] > a[r + 1] && a[r + 1] < a[r + 2]) || (a[r] < a[r + 1] && a[r + 1] > a[r + 2]))
            dp[r] = dp[r + 1];
        }
        update(1,1,n,r,dp[r]);
        for (int i = r - 1; i >= 1; i--) {
            if (i == n - 1) {
                if (a[i] == a[i + 1]) dp[i] = i;
                else dp[i] = i + 1;
            } else {
                if ((a[i] < a[i + 1] && a[i + 1] > a[i + 2]) || (a[i] > a[i + 1] && a[i + 1] < a[i + 2]))
                dp[i] = dp[i + 1];
            }
            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 (changed) {
        int to = getans(1,1,n,l,l);
        if ((a[l - 1] > a[l] && a[l] < a[l + 1]) || (a[l - 1] < a[l] && a[l] > a[l + 1])) {
            dp[l - 1] = to;
        }
        else { 
            if (a[l - 1] == a[l]) to = l - 1;
            else
            to = l; 
            dp[l - 1] = to;
        }
        //cout<<dp[l - 1]<<endl;
        update(1,1,n, l - 1, dp[l - 1]);
        for (int i = l - 2; i >= 1; i--) {
            
            if ((a[i] < a[i + 1] && a[i + 1] > a[i + 2]) || (a[i] > a[i + 1] && a[i + 1] < a[i + 2])) 
            dp[i] = dp[i + 1];
            else {
                if (a[i] == a[i + 1]) dp[i] = i;
                else dp[i] = i + 1;
            } 
            update(1,1,n,i,dp[i]);
        }
    }
}
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() {
    int q;
    cin>>n>>q;
    for (int i = 1; i <= n; i++) {
        cin>>a[i];
    }
    dp[n] = n;
    if (a[n - 1] == a[n]) dp[n - 1] = n - 1;
    else
    dp[n - 1] = n;
    for (int i = n - 2; i >= 1; i--) {
        dp[i] = i + 1;
       if (a[i] == a[i + 1]) dp[i] = i;
       if (a[i] > a[i + 1] && a[i + 1] < a[i + 2]) dp[i] = dp[i + 1];
       if (a[i] < a[i + 1] && a[i + 1] > a[i + 2]) dp[i] = dp[i + 1];
    }
    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:40:9: warning: unused variable 'to' [-Wunused-variable]
   40 |     int to = 0;
      |         ^~
Main.cpp:54:9: warning: unused variable 'ff' [-Wunused-variable]
   54 |     int ff = 0;
      |         ^~

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