| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 169082 |
2019-12-18T10:50:26 Z |
itgl |
Simple game (IZhO17_game) |
C++14 |
|
21 ms |
18680 KB |
#include<bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define mp make_pair
using namespace std;
int n,m;
int a[100005];
int tree[4000005];
int lazy[4000005];
void update(int id, int L, int R, int l, int r,int x){
if(l>R||r<L|| l>r) return;
if(lazy[id]!=0){
tree[id]+=lazy[id]*(R-L*1);
lazy[id*2]+=lazy[id];
lazy[id*2+1]+=lazy[id];
lazy[id]=0;
}
if(l<=L&&R<=r){
tree[id]+=(R-L+1)*x;
//cout << id << ' ' << tree[id] << '\n';
lazy[id*2]+=x;
lazy[id*2+1]+=x;
return;
}
update(id*2,L,(L+R)/2,l,r,x);
update(id*2+1,(L+R)/2+1,R,l,r,x);
//tree[id]=tree[id*2]+tree[id*2+1];
}
int query(int id, int L, int R, int h){
if(lazy[id] != 0)
{
tree[id] += lazy[id] * (R - L + 1);
lazy[id * 2] += lazy[id];
lazy[id * 2 + 1] += lazy[id];
lazy[id] = 0;
}
if(h>R||h<L) return 0;
if(h==R&&L==h){
return tree[id];
}
return query(id*2, L, (L + R) / 2, h)+ query(id*2+1,(L + R) / 2 + 1, R, h);
}
int main(){
cin >> n >> m;
int i,j;
for(i=1;i<=n;i++){
cin >> a[i];
if(i>1){
update(1,1,1000000,min(a[i],a[i-1])+1,max(a[i],a[i-1])-1,1);
}
}
while(m--){
int k;
cin >> k;
//cout << k;
if(k==1){
int pos, val;
cin >> pos >> val;
int t= val-a[pos];
if(pos>1&&pos<n){
if(a[pos]>a[pos-1]){
if(a[pos]<a[pos+1]){
if(t>0){
update(1,1,1000000,a[pos]+1,val,-1);
}else{
update(1,1,1000000,val+1,a[pos],1);
}
}else{
update(1,1,1000000,a[pos]+1,a[pos+1]-1,-1);
update(1,1,1000000,a[pos+1]+1,val-1,1);
}
}else{
if(t>0){
update(1,1,1000000,a[pos],val-1,1);
}else{
if(val>a[pos+1]){
update(1,1,1000000,val,a[pos]-1,-1);
}else{
update(1,1,1000000,a[pos+1]+1,a[pos]-1,-1);
update(1,1,1000000,val+1,a[pos+1]-1,1);
}
}
}
}
if(pos==1){
if(a[pos]>a[pos+1]){
if(t>0){
update(1,1,1000000,a[pos],val-1,1);
}
else{
if(val<a[pos+1]){
update(1,1,1000000,a[pos+1]+1,a[pos]-1,-1);
update(1,1,1000000,val+1,a[pos+1]-1,1);
}else{
update(1,1,1000000,val,a[pos]-1,-1);
}
}
}else{
if(t>0){
if(val>a[pos+1]){
update(1,1,1000000,a[pos]+1,a[pos+1]-1,-1);
update(1,1,1000000,a[pos+1]+1,val,1);
}else{
update(1,1,1000000,a[pos]+1,val,-1);
}
}else{
update(1,1,1000000,val+1,a[pos],-1);
}
}
}
if(pos==n){
if(a[pos]>a[pos-1]){
if(t>0){
update(1,1,1000000,a[pos],val-1,1);
}
else{
if(val>a[pos-1]){
update(1,1,1000000,val,a[pos]-1,-1);
}else{
update(1,1,1000000,a[pos-1]+1,a[pos]-1,-1);
update(1,1,1000000,val+1,a[pos-1]-1,1);
}
}
}else{
if(t>0){
if(val<a[pos-1]){
update(1,1,1000000,a[pos]+1,val,-1);
}else{
update(1,1,1000000,a[pos]+1,a[pos-1]-1,-1);
update(1,1,1000000,a[pos-1]+1,val-1,1);
}
}else{
update(1,1,1000000,val+1,a[pos],1);
}
}
}
a[pos]=val;
}
else{
int h;
cin >> h;
cout << query(1,1,1000000,h) << '\n';
}
}
return 0;
}
Compilation message
game.cpp: In function 'int main()':
game.cpp:51:9: warning: unused variable 'j' [-Wunused-variable]
int i,j;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
21 ms |
18680 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
21 ms |
18680 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
21 ms |
18680 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
