Submission #583395

#TimeUsernameProblemLanguageResultExecution timeMemory
583395lukameladzeZIGZAG (INOI20_zigzag)C++14
0 / 100
2083 ms7044 KiB
# 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;
      |         ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...