oj.uz

Submission #199749

# Submission time Handle Problem Language Result Execution time Memory
199749 2020-02-03T06:30:07 Z nafis_shifat Simple game (IZhO17_game) C++14
100 / 100
 589 ms 36972 KB 
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
#define f first
#define s second
using namespace std;

const int mxn=1e6+4;

ll tree[4*mxn]={};
ll lz[4*mxn]={};
void propogate(int b,int e,int mid,int node,int left,int right)
{
	tree[left]+=(mid-b+1)*lz[node];
    lz[left]+=lz[node];

    tree[right]+=(e-mid)*lz[node];
    lz[right]+=lz[node];

    lz[node]=0;
}
ll query(int node,int b,int e,int p)
{
	if(b>p || e<p)return 0;
	if(b==e)return tree[node];

	int m=b+e>>1;
	int l=node<<1;
	int r=l|1;
	propogate(b,e,m,node,l,r);
	
	return query(l,b,m,p)+query(r,m+1,e,p);


    
}
void update(int node, int b,int e,int l,int r,ll v)
{
	if(b>r || e<l)return;
    if(b>=l && e<=r)
    {
    	tree[node]+=(e-b+1)*v;
    	lz[node]+=v;
    	return;
    }

    int mid=b+e>>1;
    int left=node<<1;
    int right=left|1;
    propogate(b,e,mid,node,left,right);
    

    update(left,b,mid,l,r,v);
    update(right,mid+1,e,l,r,v);

}



int main()
{
	int n,q;
	cin>>n>>q;
	int h[n+1];
	for(int i=1;i<=n;i++)cin>>h[i];
    vector<pii> qs;
	for(int i=0;i<q;i++)
	{
		int t;
		cin>>t;
		if(t==1)
		{
			int p,h;
			cin>>p>>h;
			qs.push_back({p,h});
		}
		else
		{
			int h;
			cin>>h;
			qs.push_back({-1,h});
		}
	}


	for(int i=2;i<=n;i++)
	{
		update(1,1,mxn,min(h[i-1],h[i]),max(h[i-1],h[i]),1);

	}




    int ind=0;
	
	for(int i=0;i<qs.size();i++)
	{
		if(qs[i].f==-1)continue;
		for(int j=ind;j<i;j++)
		{
			cout<<query(1,1,mxn,qs[j].s)<<endl;
		}

		ind=i+1;


		int p=qs[i].f;

		if(p>1)
		{
			update(1,1,mxn,min(h[p-1],h[p]),max(h[p-1],h[p]),-1);
			int d=qs[i].s;
			update(1,1,mxn,min(h[p-1],d),max(h[p-1],d),1);

		}
		if(p<n)
		{
			update(1,1,mxn,min(h[p],h[p+1]),max(h[p],h[p+1]),-1);
			int d=qs[i].s;
			update(1,1,mxn,min(h[p+1],d),max(h[p+1],d),1);

		}

		h[p]=qs[i].s;
	}

	for(int i=ind;i<qs.size();i++)cout<<query(1,1,mxn,qs[i].s)<<endl;
	return 0;
}

Compilation message

game.cpp: In function 'long long int query(int, int, int, int)':
game.cpp:27:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=b+e>>1;
        ~^~
game.cpp: In function 'void update(int, int, int, int, int, long long int)':
game.cpp:47:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=b+e>>1;
             ~^~
game.cpp: In function 'int main()':
game.cpp:97:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<qs.size();i++)
              ~^~~~~~~~~~
game.cpp:128:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=ind;i<qs.size();i++)cout<<query(1,1,mxn,qs[i].s)<<endl;
                ~^~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 25 ms 23932 KB Output is correct
3 Correct 22 ms 23416 KB Output is correct
4 Correct 26 ms 23804 KB Output is correct
5 Correct 23 ms 23800 KB Output is correct
6 Correct 23 ms 23672 KB Output is correct
7 Correct 19 ms 18936 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 25 ms 23932 KB Output is correct
3 Correct 22 ms 23416 KB Output is correct
4 Correct 26 ms 23804 KB Output is correct
5 Correct 23 ms 23800 KB Output is correct
6 Correct 23 ms 23672 KB Output is correct
7 Correct 19 ms 18936 KB Output is correct
8 Correct 321 ms 2772 KB Output is correct
9 Correct 508 ms 36840 KB Output is correct
10 Correct 508 ms 36844 KB Output is correct
11 Correct 311 ms 2792 KB Output is correct
12 Correct 389 ms 4844 KB Output is correct
13 Correct 413 ms 36584 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 25 ms 23932 KB Output is correct
3 Correct 22 ms 23416 KB Output is correct
4 Correct 26 ms 23804 KB Output is correct
5 Correct 23 ms 23800 KB Output is correct
6 Correct 23 ms 23672 KB Output is correct
7 Correct 19 ms 18936 KB Output is correct
8 Correct 321 ms 2772 KB Output is correct
9 Correct 508 ms 36840 KB Output is correct
10 Correct 508 ms 36844 KB Output is correct
11 Correct 311 ms 2792 KB Output is correct
12 Correct 389 ms 4844 KB Output is correct
13 Correct 413 ms 36584 KB Output is correct
14 Correct 545 ms 36716 KB Output is correct
15 Correct 575 ms 36852 KB Output is correct
16 Correct 564 ms 36972 KB Output is correct
17 Correct 572 ms 36716 KB Output is correct
18 Correct 589 ms 36716 KB Output is correct