| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 593002 |
2022-07-10T06:02:44 Z |
radal |
ZIGZAG (INOI20_zigzag) |
C++17 |
|
476 ms |
76896 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);
//debug(l);
//debug(r);
//debug(seg[v][6]);
}
inline void passza(int v){
za[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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
1684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
476 ms |
76896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
1684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
1684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
