oj.uz

Submission #879383

# Submission time Handle Problem Language Result Execution time Memory
879383 2023-11-27T08:57:05 Z 8pete8 Simple game (IZhO17_game) C++14
100 / 100
 185 ms 24832 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);
#pragma GCC optimize ("03,unroll-lopps")
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:30:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   30 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
game.cpp:35:28: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   35 | void update(int pos,int val){for(int i=pos;i<=n;i+=i&-i)fwk[i]+=val;}
      |                            ^
game.cpp:36:16: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   36 | int qry(int pos){
      |                ^
game.cpp:45:29: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   45 | void upd(int l,int r,int yes){
      |                             ^
game.cpp: In function 'void upd(long long int, long long int, long long int)':
game.cpp:46: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]
   46 |  if(l<0||r<0||l>=v.size()||r>=v.size())return;
      |               ~^~~~~~~~~~
game.cpp:46: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]
   46 |  if(l<0||r<0||l>=v.size()||r>=v.size())return;
      |                            ~^~~~~~~~~~
game.cpp: At global scope:
game.cpp:51:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   51 | int32_t main(){
      |              ^
game.cpp: In function 'int32_t main()':
game.cpp:66: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]
   66 |  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 1 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 856 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 856 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 26 ms 4308 KB Output is correct
9 Correct 170 ms 24832 KB Output is correct
10 Correct 128 ms 24828 KB Output is correct
11 Correct 22 ms 5072 KB Output is correct
12 Correct 59 ms 9364 KB Output is correct
13 Correct 76 ms 15960 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 856 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 26 ms 4308 KB Output is correct
9 Correct 170 ms 24832 KB Output is correct
10 Correct 128 ms 24828 KB Output is correct
11 Correct 22 ms 5072 KB Output is correct
12 Correct 59 ms 9364 KB Output is correct
13 Correct 76 ms 15960 KB Output is correct
14 Correct 155 ms 24320 KB Output is correct
15 Correct 150 ms 24576 KB Output is correct
16 Correct 185 ms 24244 KB Output is correct
17 Correct 162 ms 24320 KB Output is correct
18 Correct 154 ms 24192 KB Output is correct