Submission #1003391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003391		vjudge1	ZIGZAG (INOI20_zigzag)	C++17	8 / 100	2069 ms	8372 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define oo 1e9

const int MAX = 3e5 + 5;
int n, q;
int arr[MAX];
int ans[MAX][2];

void solve(){
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
    }
    while(q--){
        char t; cin >> t;
        if(t == '*'){
            int l, r; cin >> l >> r;
            for(int i = l; i <= r; i++) arr[i] *= -1;
        }
        if(t == '+'){
            int l, r, v; cin >> l >> r >> v;
            for(int i = l; i <= r; i++) arr[i] += v;
        }
        if(t == '?'){
            int l, r; cin >> l >> r;
            for(int i = l; i <= r; i++) ans[i][0] = ans[i][1] = 1;
            int res = 1;
            for(int i = r - 1; i >= l; i--){
                if(arr[i] > arr[i + 1]) ans[i][1] = ans[i + 1][0] + 1;
                if(arr[i] < arr[i + 1]) ans[i][0] = ans[i + 1][1] + 1;
                res += max(ans[i][0], ans[i][1]);
            }
            cout << res << "\n";
        }
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while(t--){
        solve();
    }
}

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