oj.uz

답안 #172130

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
172130 2019-12-31T10:18:08 Z MvC Simple game (IZhO17_game) C++11
100 / 100
 82 ms 6936 KB 
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e5+50;
const int lim=1e6;
const int mod=1e9+7;
using namespace std;
int n,m,a[nmax],i,x,tp,fw[lim+5];
void upd(int i,int v)
{
	for(;i<=lim;i+=i&(-i))fw[i]+=v;
}
int qry(int i)
{
	int rs=0;
	for(;i>=1;i-=i&(-i))rs+=fw[i];
	return rs;
}
void chg(int l,int r,int _)
{
	if(a[l]>a[r])
	{
		upd(a[r],_);
		upd(a[l]+1,-_);
	}
	else
	{
		upd(a[l],_);
		upd(a[r]+1,-_);
	}
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n>>m;
	for(i=1;i<=n;i++)cin>>a[i];
	for(i=2;i<=n;i++)chg(i-1,i,1);
	while(m--)
	{
		cin>>tp;
		if(tp==1)
		{
			cin>>i>>x;
			if(i>1)chg(i-1,i,-1);
			if(i<n)chg(i,i+1,-1);
			a[i]=x;
			if(i>1)chg(i-1,i,1);
			if(i<n)chg(i,i+1,1);
		}
		else
		{
			cin>>x;
			cout<<qry(x)<<'\n';
		}
	}
	return 0;
}

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 5 ms 3964 KB Output is correct
3 Correct 5 ms 3960 KB Output is correct
4 Correct 5 ms 3960 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 5 ms 3960 KB Output is correct
7 Correct 3 ms 376 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 5 ms 3964 KB Output is correct
3 Correct 5 ms 3960 KB Output is correct
4 Correct 5 ms 3960 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 5 ms 3960 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 45 ms 1784 KB Output is correct
9 Correct 54 ms 6904 KB Output is correct
10 Correct 55 ms 6904 KB Output is correct
11 Correct 46 ms 1656 KB Output is correct
12 Correct 50 ms 2936 KB Output is correct
13 Correct 51 ms 2808 KB Output is correct

Subtask #3
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 5 ms 3964 KB Output is correct
3 Correct 5 ms 3960 KB Output is correct
4 Correct 5 ms 3960 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 5 ms 3960 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 45 ms 1784 KB Output is correct
9 Correct 54 ms 6904 KB Output is correct
10 Correct 55 ms 6904 KB Output is correct
11 Correct 46 ms 1656 KB Output is correct
12 Correct 50 ms 2936 KB Output is correct
13 Correct 51 ms 2808 KB Output is correct
14 Correct 73 ms 6876 KB Output is correct
15 Correct 76 ms 6936 KB Output is correct
16 Correct 74 ms 6904 KB Output is correct
17 Correct 79 ms 6904 KB Output is correct
18 Correct 82 ms 6856 KB Output is correct