Submission #91410

#	Time	Username	Problem	Language	Result	Execution time	Memory
91410		emil_physmath	Simple game (IZhO17_game)	C++17	22 / 100	1072 ms	4940 KiB

game

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

pair<int, int> h[100005];
char state[100005], temp[100005];

void SolveOne(int n, int m);
int BruteForce(char * l, char * r);
int main()
{
	int n, m;
	cin>>n>>m;
	for (int i=0; i<n; i++)
	{
		cin>>h[i].first;
		h[i].second=i;
	}
	if (n*m<=70000000)
	{
		SolveOne(n, m);
		return 0;
	}

	vector<pair<int, int>> q;
	for (int t=0; t<m; t++)
	{
		int temp, H;
		cin>>temp>>H;
		q.push_back(make_pair(H, t));
	}
	sort(q.begin(), q.end());
	int ans=0;
	for (int i=0; i<n; i++)
	{
		temp[i]=state[i]=(h[i].first<q[0].first?'<':'>');
		if (i && state[i]!=state[i-1])
			ans++;
	}
	cout<<ans<<'\n';
	sort(h, h+n);
	int lessFrom=0;
	for (int t=1; t<q.size(); t++)
	{
		vector<int> curChange;
		while (lessFrom<n)
		{
			if (h[lessFrom].first>q[t].first) break;
			int curLessInd=h[lessFrom].second/*, curLessH=h[lessFrom].first*/;
			lessFrom++;
			if (state[curLessInd]=='<') continue;
			curChange.push_back(curLessInd);
		}
		sort(curChange.begin(), curChange.end());
		for (int i=0; i<curChange.size(); i++)
			temp[curChange[i]]='<';
		int l=0, r=0;
		while (l<curChange.size())
		{
			while (r+1<curChange.size() && curChange[r+1]==curChange[r]+1)
				r++;
			ans+=BruteForce(l?temp+l-1:temp+l, r+1<n?temp+r+1:temp+r)-
				BruteForce(l?state+l-1:state+l, r+1<n?state+r+1:state+r);
			l=r+1;
		}
		for (int i=0; i<curChange.size(); i++)
			state[curChange[i]]=temp[curChange[i]];
		cout<<ans<<'\n';
	}

	char I;
	cin >> I;
	return 0;
}
/*
4 2
3 4 1 6
2 2
2 5
*/

int BruteForce(char * l, char * r)
{
	int ans=0;
	l++;
	while (l<=r)
	{
		if (*l!=*(l-1))
			ans++;
		l++;
	}
	return ans;
}

void SolveOne(int n, int m)
{
	while (m--)
	{
		int type;
		cin>>type;
		if (type==1)
		{
			int pos, val;
			cin>>pos>>val;
			h[pos-1].first=val;
		}
		else
		{
			int H, ans=0;
			cin>>H;
			char curState='0';
			for (int i=0; i<n; i++)
				if (h[i].first<H)
				{
					if (curState=='>')
						ans++;
					curState='<';
				}
				else
				{
					if (curState=='<')
						ans++;
					curState='>';
				}
			cout<<ans<<'\n';
		}
	}
}

Compilation message (stderr)

game.cpp: In function 'int main()':
game.cpp:45:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int t=1; t<q.size(); t++)
                ~^~~~~~~~~
game.cpp:57:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<curChange.size(); i++)
                 ~^~~~~~~~~~~~~~~~~
game.cpp:60:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (l<curChange.size())
          ~^~~~~~~~~~~~~~~~~
game.cpp:62:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (r+1<curChange.size() && curChange[r+1]==curChange[r]+1)
           ~~~^~~~~~~~~~~~~~~~~
game.cpp:68:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<curChange.size(); i++)
                 ~^~~~~~~~~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 0 / 27
• Subtask 3: 0 / 51