oj.uz

Submission #91860

# Submission time Handle Problem Language Result Execution time Memory
91860 2018-12-30T14:28:50 Z emil_physmath Simple game (IZhO17_game) C++17
100 / 100
 605 ms 17836 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 18 ms 15480 KB Output is correct
3 Correct 16 ms 15224 KB Output is correct
4 Correct 18 ms 15352 KB Output is correct
5 Correct 18 ms 15480 KB Output is correct
6 Correct 19 ms 15480 KB Output is correct
7 Correct 15 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 18 ms 15480 KB Output is correct
3 Correct 16 ms 15224 KB Output is correct
4 Correct 18 ms 15352 KB Output is correct
5 Correct 18 ms 15480 KB Output is correct
6 Correct 19 ms 15480 KB Output is correct
7 Correct 15 ms 12920 KB Output is correct
8 Correct 243 ms 956 KB Output is correct
9 Correct 424 ms 17716 KB Output is correct
10 Correct 415 ms 17696 KB Output is correct
11 Correct 239 ms 1032 KB Output is correct
12 Correct 298 ms 1964 KB Output is correct
13 Correct 341 ms 17836 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 18 ms 15480 KB Output is correct
3 Correct 16 ms 15224 KB Output is correct
4 Correct 18 ms 15352 KB Output is correct
5 Correct 18 ms 15480 KB Output is correct
6 Correct 19 ms 15480 KB Output is correct
7 Correct 15 ms 12920 KB Output is correct
8 Correct 243 ms 956 KB Output is correct
9 Correct 424 ms 17716 KB Output is correct
10 Correct 415 ms 17696 KB Output is correct
11 Correct 239 ms 1032 KB Output is correct
12 Correct 298 ms 1964 KB Output is correct
13 Correct 341 ms 17836 KB Output is correct
14 Correct 588 ms 17464 KB Output is correct
15 Correct 605 ms 17536 KB Output is correct
16 Correct 595 ms 17408 KB Output is correct
17 Correct 595 ms 17460 KB Output is correct
18 Correct 597 ms 17552 KB Output is correct