oj.uz

Submission #48398

# Submission time Handle Problem Language Result Execution time Memory
48398 2018-05-12T17:29:06 Z aleksami Simple game (IZhO17_game) C++14
100 / 100
 512 ms 35412 KB 
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define MAXH 1000005

int tree[4*MAXH];
int lazy[4*MAXH];
int a[MAXN];

void push(int node,int left,int right)
{
	if(lazy[node]!=0)
	{
		tree[node]+=lazy[node]*(right-left+1);
		if(left != right)
		{
			lazy[node*2]+=lazy[node];
			lazy[node*2+1]+=lazy[node];
		}
		lazy[node]=0;
	}
}
void update(int node,int left,int right,int l,int r,int val)
{
	push(node,left,right);
	if(left >= l && right <= r)
	{
		lazy[node]+=val;
		push(node,left,right);
		return ;
	}
	int mid=(left+right)>>1;
	if(l <= mid)update(node*2,left,mid,l,r,val);
	if(r > mid)update(node*2+1,mid+1,right,l,r,val);
	tree[node]=tree[node*2]+tree[node*2+1];
}
int query(int node,int left,int right,int l,int r)
{
	push(node,left,right);
	if(left >= l && right <= r)return tree[node];
	int mid=(left+right)>>1;
	int ret=0;
	if(l <= mid)ret += query(node*2,left,mid,l,r);
	if(r > mid)ret += query(node*2+1,mid+1,right,l,r);
	return ret;
}


int main() {
	ios_base::sync_with_stdio(false);
	int n,q;
	cin >> n >> q;
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	for(int i = 0; i < n-1; i++)
	{
		int l = min(a[i],a[i+1]);
		int r = max(a[i],a[i+1]);
		if(l!=r)update(1,1,MAXH-1,l,r,1);
		else update(1,1,MAXH-1,l,r,2);
	}
	while(q--)
	{
		int t;
		cin >> t;
		if(t==1)
		{
			int pos,val;
			cin >> pos >> val;
			pos--;
			if(pos > 0)
            {
              if(a[pos-1]!=a[pos])update(1,1,MAXH-1,min(a[pos-1],a[pos]),max(a[pos-1],a[pos]),-1);
              else update(1,1,MAXH-1,min(a[pos-1],a[pos]),max(a[pos-1],a[pos]),-2);
            }
          	if(pos < n-1)
            {
              if(a[pos+1]!=a[pos])update(1,1,MAXH-1,min(a[pos+1],a[pos]),max(a[pos+1],a[pos]),-1);
              else update(1,1,MAXH-1,min(a[pos+1],a[pos]),max(a[pos+1],a[pos]),-2);
            }
          a[pos]=val;
          if(pos > 0)
            {
              if(a[pos-1]!=a[pos])update(1,1,MAXH-1,min(a[pos-1],a[pos]),max(a[pos-1],a[pos]),+1);
              else update(1,1,MAXH-1,min(a[pos-1],a[pos]),max(a[pos-1],a[pos]),+2);
            }
          	if(pos < n-1)
            {
              if(a[pos+1]!=a[pos])update(1,1,MAXH-1,min(a[pos+1],a[pos]),max(a[pos+1],a[pos]),+1);
              else update(1,1,MAXH-1,min(a[pos+1],a[pos]),max(a[pos+1],a[pos]),+2);
            }
		}
		else
		{
			int h;
			cin >> h;
			cout << query(1,1,MAXH-1,h,h) << "\n";
		}
	}
	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 15 ms 14952 KB Output is correct
3 Correct 15 ms 15020 KB Output is correct
4 Correct 15 ms 15280 KB Output is correct
5 Correct 16 ms 15280 KB Output is correct
6 Correct 16 ms 15292 KB Output is correct
7 Correct 12 ms 15292 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 15 ms 14952 KB Output is correct
3 Correct 15 ms 15020 KB Output is correct
4 Correct 15 ms 15280 KB Output is correct
5 Correct 16 ms 15280 KB Output is correct
6 Correct 16 ms 15292 KB Output is correct
7 Correct 12 ms 15292 KB Output is correct
8 Correct 221 ms 15292 KB Output is correct
9 Correct 350 ms 20496 KB Output is correct
10 Correct 358 ms 22252 KB Output is correct
11 Correct 212 ms 22252 KB Output is correct
12 Correct 265 ms 22252 KB Output is correct
13 Correct 302 ms 25860 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 15 ms 14952 KB Output is correct
3 Correct 15 ms 15020 KB Output is correct
4 Correct 15 ms 15280 KB Output is correct
5 Correct 16 ms 15280 KB Output is correct
6 Correct 16 ms 15292 KB Output is correct
7 Correct 12 ms 15292 KB Output is correct
8 Correct 221 ms 15292 KB Output is correct
9 Correct 350 ms 20496 KB Output is correct
10 Correct 358 ms 22252 KB Output is correct
11 Correct 212 ms 22252 KB Output is correct
12 Correct 265 ms 22252 KB Output is correct
13 Correct 302 ms 25860 KB Output is correct
14 Correct 491 ms 27568 KB Output is correct
15 Correct 487 ms 29616 KB Output is correct
16 Correct 512 ms 31544 KB Output is correct
17 Correct 488 ms 33412 KB Output is correct
18 Correct 498 ms 35412 KB Output is correct