oj.uz

Submission #1018877

# Submission time Handle Problem Language Result Execution time Memory
1018877 2024-07-10T10:30:31 Z Minbaev Collider (IZhO11_collider) C++17
100 / 100
 804 ms 95468 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
 
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")
 
using namespace std;
using namespace __gnu_pbds;
 
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define f first
#define s second
#define int long long
#define pii pair<int,int>
 
template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}
 
template<class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag,
    tree_order_statistics_node_update>;
 
const int inf = 1e11 + 7;
const int mod = 1e9 + 7;
const int N = 3e5 + 5;

int binpow(int a, int b){
	if(b == 0)return 1;
	if(b % 2 == 0){
		int c = binpow(a,b/2);
		return (c*c)%mod;
	}
	return (binpow(a,b-1)*a)%mod;
}

int divi(int a, int b){
	return (a*(binpow(b,mod-2)))%mod;
}

int n,m,k;

int res1(char ch){
	if(ch == 'x')return 1;
	if(ch == 'y')return 2;
	if(ch == 'z')return 3;
}

char res2(int a){
	if(a == 1)return 'x';
	if(a == 2)return 'y';
	if(a == 3)return 'z';
}

void solve(){
	
	cin >> n >> m;
	Tree<pair<long double, int>>st;
	
	st.insert({0,-1});
	for(int i = 1;i<=n;i++){
		char ch;
		cin >> ch;
		st.insert({i*1e11, res1(ch)});
	}
	st.insert({1e25,-1});
	
	while(m--){
		char ch;
		cin >> ch;
		if(ch == 'q'){
			int a;
			cin >> a;
			auto to = st.find_by_order(a);
			cout << res2((*to).s) << "\n";
		}
		else{
			int l,r;
			cin >> l >> r;
			
			auto to = st.find_by_order(l);
			int sec = (*to).s;
			st.erase(to);
			
			auto it1 = st.find_by_order(r-1);
			auto it2 = st.find_by_order(r);
			long double val = ((*it1).f+(*it2).f)/2.0;
			st.insert({val,sec});
		}
	}
	
}
 
 signed main()
{
//	freopen("seq.in", "r", stdin);
//  freopen("seq.out", "w", stdout);

	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	int tt=1;//cin>>tt;
	while(tt--)solve();
 
}

Compilation message

collider.cpp: In function 'long long int res1(char)':
collider.cpp:48:1: warning: control reaches end of non-void function [-Wreturn-type]
   48 | }
      | ^
collider.cpp: In function 'char res2(long long int)':
collider.cpp:54:1: warning: control reaches end of non-void function [-Wreturn-type]
   54 | }
      | ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 5 ms 652 KB Output is correct
3 Correct 58 ms 9904 KB Output is correct
4 Correct 606 ms 76192 KB Output is correct
5 Correct 604 ms 76368 KB Output is correct
6 Correct 697 ms 85840 KB Output is correct
7 Correct 793 ms 95468 KB Output is correct
8 Correct 782 ms 95248 KB Output is correct
9 Correct 804 ms 95424 KB Output is correct
10 Correct 802 ms 95316 KB Output is correct