Submission #91860

#	Time	Username	Problem	Language	Result	Execution time	Memory
91860		emil_physmath	Simple game (IZhO17_game)	C++17	100 / 100	605 ms	17836 KiB

game

#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 (stderr)

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 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51