oj.uz

Submission #91859

# Submission time Handle Problem Language Result Execution time Memory
91859 2018-12-30T14:26:27 Z emil_physmath Simple game (IZhO17_game) C++17
100 / 100
 627 ms 19516 KB 
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

int h[100005], tree[4000005] = {0}, lazy[4000000] = {0};
int getSumUtil(int ss, int se, int qs, int qe, int si);
int getSum(int q);
void updateRangeUtil(int si, int ss, int se, int us, int ue, int diff);
void updateRange(int us, int ue, int diff);

int Ans(int l, int m, int r, int H);
int RealAns(int n, int H)
{
	int ans=0;
	char curState='0';
	for (int i=0; i<n; i++)
		if (h[i]<H)
		{
			if (curState=='>')
				ans++;
			curState='<';
		}
		else
		{
			if (curState=='<')
				ans++;
			curState='>';
		}
	return ans;
}
int main()
{
	int n, m;
	cin>>n>>m;
	for (int i=0; i<n; i++)
		scanf("%d", h+i);
	for (int i=1; i<n; i++)
	{
		updateRange(min(h[i-1], h[i]), max(h[i-1], h[i]), 1);
		if (i!=n-1) updateRange(h[i], h[i], -1);
	}
	/*
	cout<<"\n\n";
	for (int H=1; H<=15; H++)
		cout<<H<<": "<<getSum(H)<<'\n';
	*/
	while (m--)
	{
		int type;
		cin>>type;
		if (type==1)
		{
			int i, H;
			cin>>i>>H; i--;
			int l_h=(i?h[i-1]:-1), r_h=(i+1<n?h[i+1]:-1);
			if (l_h!=-1) updateRange(min(l_h, h[i]), max(l_h, h[i]), -1);
			if (r_h!=-1) updateRange(min(h[i], r_h), max(h[i], r_h), -1);
			if (l_h!=-1 && r_h!=-1) updateRange(h[i], h[i], 1);
			if (l_h!=-1) updateRange(min(l_h, H), max(l_h, H), 1);
			if (r_h!=-1) updateRange(min(H, r_h), max(H, r_h), 1);
			if (l_h!=-1 && r_h!=-1) updateRange(H, H, -1);
			/*
			updateRange(min(h[i], H)+1, max(h[i], H)-1,
				Ans(l_h, H, r_h, min(h[i], H)+1)-Ans(l_h, h[i], r_h, min(h[i], H)+1));

			updateRange(h[i], h[i], Ans(l_h, H, r_h, h[i])-Ans(l_h, h[i], r_h, h[i]));
			updateRange(H, H, Ans(l_h, H, r_h, H)-Ans(l_h, h[i], r_h, H));
			*/
			h[i]=H;
			/*
			for (int H=1; H<=5; H++)
				cout<<H<<": "<<getSum(H)<<'\n';
			*/
		}
		else
		{
			int H;
			cin>>H;
			/*
			cout<<"\t\t"<<getSum(H)<<".\n";
			cout<<"Real ans = \t"<<RealAns(n, H)<<".\n";
			*/
			cout<<getSum(H)<<'\n';
		}
	}
 
	char I;
	cin >> I;
	return 0;
}
/*
9 1000000
2 5 3 8 1 10 8 15 5
*/

int Ans(int l, int m, int r, int H)
{
	int ans=0;
	if (l!=-1 && H>=min(l, m) && H<=max(l, m)) ans++;
	if (r!=-1 && H>=min(m, r) && H<=max(m, r)) ans++;
	if (H==m) ans--;
	return ans;
}
int getSumUtil(int ss, int se, int qs, int qe, int si) 
{
    if (lazy[si] != 0) 
    {
        tree[si] += (se-ss+1)*lazy[si];
        if (ss != se) 
        {
            lazy[si*2+1] += lazy[si]; 
            lazy[si*2+2] += lazy[si]; 
        }
        lazy[si] = 0; 
    }
    if (ss>se || ss>qe || se<qs) 
        return 0;
    if (ss>=qs && se<=qe)
        return tree[si];
    int mid = (ss + se)/2; 
    return getSumUtil(ss, mid, qs, qe, 2*si+1) + 
           getSumUtil(mid+1, se, qs, qe, 2*si+2); 
}
int getSum(int q)
{
	// q>=0 && q<n
	int n=1000001;
    return getSumUtil(0, n-1, q-1, q-1, 0);
}
void updateRangeUtil(int si, int ss, int se, int us, int ue, int diff) 
{ 
    if (lazy[si] != 0) 
    { 
        tree[si] += (se-ss+1)*lazy[si]; 
        if (ss != se) 
        { 
            lazy[si*2 + 1]   += lazy[si]; 
            lazy[si*2 + 2]   += lazy[si]; 
        }
        lazy[si] = 0; 
    }
    if (ss>se || ss>ue || se<us) 
        return ;
    if (ss>=us && se<=ue) 
    { 
        tree[si] += (se-ss+1)*diff;
        if (ss != se) 
        {
            lazy[si*2 + 1]   += diff; 
            lazy[si*2 + 2]   += diff; 
        } 
        return; 
    }
    int mid = (ss+se)/2; 
    updateRangeUtil(si*2+1, ss, mid, us, ue, diff); 
    updateRangeUtil(si*2+2, mid+1, se, us, ue, diff);
    tree[si] = tree[si*2+1] + tree[si*2+2]; 
}
void updateRange(int us, int ue, int diff)
{
	if (us>ue) return;
	int n=1000001;
	updateRangeUtil(0, 0, n-1, us-1, ue-1, diff);
}

Compilation message

game.cpp: In function 'int main()':
game.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", h+i);
   ~~~~~^~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 19 ms 15480 KB Output is correct
3 Correct 17 ms 15224 KB Output is correct
4 Correct 19 ms 15480 KB Output is correct
5 Correct 18 ms 15480 KB Output is correct
6 Correct 18 ms 15480 KB Output is correct
7 Correct 14 ms 12920 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 19 ms 15480 KB Output is correct
3 Correct 17 ms 15224 KB Output is correct
4 Correct 19 ms 15480 KB Output is correct
5 Correct 18 ms 15480 KB Output is correct
6 Correct 18 ms 15480 KB Output is correct
7 Correct 14 ms 12920 KB Output is correct
8 Correct 245 ms 1796 KB Output is correct
9 Correct 385 ms 19448 KB Output is correct
10 Correct 422 ms 19320 KB Output is correct
11 Correct 243 ms 1628 KB Output is correct
12 Correct 304 ms 3320 KB Output is correct
13 Correct 339 ms 19300 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 19 ms 15480 KB Output is correct
3 Correct 17 ms 15224 KB Output is correct
4 Correct 19 ms 15480 KB Output is correct
5 Correct 18 ms 15480 KB Output is correct
6 Correct 18 ms 15480 KB Output is correct
7 Correct 14 ms 12920 KB Output is correct
8 Correct 245 ms 1796 KB Output is correct
9 Correct 385 ms 19448 KB Output is correct
10 Correct 422 ms 19320 KB Output is correct
11 Correct 243 ms 1628 KB Output is correct
12 Correct 304 ms 3320 KB Output is correct
13 Correct 339 ms 19300 KB Output is correct
14 Correct 598 ms 19516 KB Output is correct
15 Correct 627 ms 19484 KB Output is correct
16 Correct 598 ms 19448 KB Output is correct
17 Correct 590 ms 19448 KB Output is correct
18 Correct 613 ms 19388 KB Output is correct