oj.uz

Submission #494947

# Submission time Handle Problem Language Result Execution time Memory
494947 2021-12-17T16:48:41 Z luka1234 Simple game (IZhO17_game) C++14
100 / 100
 227 ms 9128 KB 
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
using namespace std;
int f1[1000002];
int f2[1000002];
int n,m;
int nmax=1000001;
int h[100001];
int getsum1(int v){
    int ans=0;
    for(int i=v;i>=1;i=(i&(i-1))){
        ans+=f1[i];
    }
    return ans;
}
int getsum2(int v){
    int ans=0;
    for(int i=v;i>=1;i=(i&(i-1))){
        ans+=f2[i];
    }
    return ans;
}
void update1(int v,int x){
    for(int i=v;i<=nmax;i=2*i-(i&(i-1))){
        f1[i]+=x;
    }
}
void update2(int v,int x){
    for(int i=v;i<=nmax;i=2*i-(i&(i-1))){
        f2[i]+=x;
    }
}
int rangesum(int l,int r){
    int sum1=getsum1(r)+getsum2(r)*r;
    int sum2=getsum1(l-1)+getsum2(l-1)*(l-1);
    return(sum1-sum2);
}
void rangeupdate(int l,int r,int x){
	int u1=-(l-1)*x;
    int u2=r*x;
    update1(l,u1);
    update1(r+1,u2);
    update2(l,x);
    update2(r+1,-x);
}
int main(){
	cin>>n>>m;
	for(int k=1;k<=n;k++){
		cin>>h[k];
	}
	for(int k=2;k<=n;k++){
		int l=min(h[k],h[k-1]);
		int r=max(h[k],h[k-1]);
		rangeupdate(l,r,1);
	}
	while(m--){
		int ind;
		cin>>ind;
		if(ind==1){
			int pos,val;
			cin>>pos>>val;
			if(pos>1&&pos<n){
				int l1=min(h[pos],h[pos-1]);
				int r1=max(h[pos],h[pos-1]);
				int l2=min(h[pos],h[pos+1]);
				int r2=max(h[pos],h[pos+1]);
				h[pos]=val;
				int l3=min(h[pos],h[pos-1]);
				int r3=max(h[pos],h[pos-1]);
				int l4=min(h[pos],h[pos+1]);
				int r4=max(h[pos],h[pos+1]);
				rangeupdate(l1,r1,-1);
				rangeupdate(l2,r2,-1);
				rangeupdate(l3,r3,1);
				rangeupdate(l4,r4,1);
			}
			else{
				if(pos==1){
					int l2=min(h[pos],h[pos+1]);
				    int r2=max(h[pos],h[pos+1]);
				    h[pos]=val;
				    int l4=min(h[pos],h[pos+1]);
				    int r4=max(h[pos],h[pos+1]);
				    rangeupdate(l2,r2,-1);
				    rangeupdate(l4,r4,1);
				}
				else{
					int l1=min(h[pos],h[pos-1]);
				    int r1=max(h[pos],h[pos-1]);
				    h[pos]=val;
				    int l3=min(h[pos],h[pos-1]);
				    int r3=max(h[pos],h[pos-1]);
				    rangeupdate(l1,r1,-1);
				    rangeupdate(l3,r3,1);
				}
			}
		}
		else{
			int y;
			cin>>y;
			int ans=rangesum(y,y);
			cout<<ans<<"\n";
		}
	}
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 5 ms 7756 KB Output is correct
3 Correct 5 ms 7756 KB Output is correct
4 Correct 5 ms 7756 KB Output is correct
5 Correct 5 ms 7628 KB Output is correct
6 Correct 5 ms 7756 KB Output is correct
7 Correct 5 ms 332 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 5 ms 7756 KB Output is correct
3 Correct 5 ms 7756 KB Output is correct
4 Correct 5 ms 7756 KB Output is correct
5 Correct 5 ms 7628 KB Output is correct
6 Correct 5 ms 7756 KB Output is correct
7 Correct 5 ms 332 KB Output is correct
8 Correct 188 ms 964 KB Output is correct
9 Correct 227 ms 9128 KB Output is correct
10 Correct 227 ms 9044 KB Output is correct
11 Correct 181 ms 920 KB Output is correct
12 Correct 204 ms 1568 KB Output is correct
13 Correct 212 ms 1416 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 5 ms 7756 KB Output is correct
3 Correct 5 ms 7756 KB Output is correct
4 Correct 5 ms 7756 KB Output is correct
5 Correct 5 ms 7628 KB Output is correct
6 Correct 5 ms 7756 KB Output is correct
7 Correct 5 ms 332 KB Output is correct
8 Correct 188 ms 964 KB Output is correct
9 Correct 227 ms 9128 KB Output is correct
10 Correct 227 ms 9044 KB Output is correct
11 Correct 181 ms 920 KB Output is correct
12 Correct 204 ms 1568 KB Output is correct
13 Correct 212 ms 1416 KB Output is correct
14 Correct 219 ms 8676 KB Output is correct
15 Correct 206 ms 8704 KB Output is correct
16 Correct 208 ms 8740 KB Output is correct
17 Correct 222 ms 8696 KB Output is correct
18 Correct 217 ms 8744 KB Output is correct