oj.uz

Submission #879382

# Submission time Handle Problem Language Result Execution time Memory
879382 2023-11-27T08:56:27 Z 8pete8 Simple game (IZhO17_game) C++14
100 / 100
 185 ms 26456 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
//#define p push
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
#define int long long
const int mod=9901,mxn=5*1e5+5,inf=1e18,lg=25,minf=-1e18;
int fwk[mxn+10],n;
void update(int pos,int val){for(int i=pos;i<=n;i+=i&-i)fwk[i]+=val;}
int qry(int pos){
	int sum=0;
	for(int i=pos;i>0;i-=(i&-i))sum+=fwk[i];
	return sum;
}
vector<int>v;
vector<ppii>q;
set<int>a;
unordered_map<int,int>p;
void upd(int l,int r,int yes){
	if(l<0||r<0||l>=v.size()||r>=v.size())return;
	if(v[r]<v[l])swap(l,r);
	update(p[v[l]],yes);
	update(p[v[r]]+1,-yes);
}
int32_t main(){
    fastio
	int m,pos,val;cin>>n>>m;
	v.resize(n);
	for(int i=0;i<n;i++)cin>>v[i],a.insert(v[i]);
	for(int i=0;i<m;i++){
		int t;cin>>t;
		if(t==1)cin>>pos>>val;
		else cin>>val;
		a.insert(val);
		q.pb({t,{val,pos-1}});
	}
	n=a.size();
	int idx=0;
	for(auto i:a)idx++,p[i]=idx;
	for(int i=0;i<v.size()-1;i++)upd(i,i+1,1);
	for(auto i:q){
		if(i.f==2)cout<<qry(p[i.s.f])<<'\n';
		else{
			upd(i.s.s-1,i.s.s,-1);
			upd(i.s.s,i.s.s+1,-1);
			v[i.s.s]=i.s.f;
			upd(i.s.s-1,i.s.s,1);
			upd(i.s.s,i.s.s+1,1);
		}
	}
}

Compilation message

game.cpp: In function 'void upd(long long int, long long int, long long int)':
game.cpp:45:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  if(l<0||r<0||l>=v.size()||r>=v.size())return;
      |               ~^~~~~~~~~~
game.cpp:45:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  if(l<0||r<0||l>=v.size()||r>=v.size())return;
      |                            ~^~~~~~~~~~
game.cpp: In function 'int32_t main()':
game.cpp:65:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(int i=0;i<v.size()-1;i++)upd(i,i+1,1);
      |              ~^~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 472 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 472 KB Output is correct
8 Correct 29 ms 6352 KB Output is correct
9 Correct 165 ms 26456 KB Output is correct
10 Correct 135 ms 26456 KB Output is correct
11 Correct 21 ms 5072 KB Output is correct
12 Correct 65 ms 10264 KB Output is correct
13 Correct 72 ms 16640 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 472 KB Output is correct
8 Correct 29 ms 6352 KB Output is correct
9 Correct 165 ms 26456 KB Output is correct
10 Correct 135 ms 26456 KB Output is correct
11 Correct 21 ms 5072 KB Output is correct
12 Correct 65 ms 10264 KB Output is correct
13 Correct 72 ms 16640 KB Output is correct
14 Correct 185 ms 26040 KB Output is correct
15 Correct 183 ms 26216 KB Output is correct
16 Correct 147 ms 26112 KB Output is correct
17 Correct 156 ms 26156 KB Output is correct
18 Correct 150 ms 26108 KB Output is correct