제출 #1188320

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1188320		SmuggingSpun	Specijacija (COCI20_specijacija)	C++20	0 / 110	444 ms	76392 KiB

Main

#include<bits/stdc++.h>
#define taskname "E"
using namespace std;
typedef long long ll;
int n, q, t;
int level(ll x){
	int low = 2, high = n + 1, ans = 1;
	while(low <= high){
		int mid = (low + high) >> 1;
		if(((1LL * mid * (mid - 1)) >> 1LL) < x){
			low = (ans = mid) + 1;
		}
		else{
			high = mid - 1;
		}
	}
	return ans;
}
int level_id(ll x){
	int lvl = level(x);
	return x - ((1LL * lvl * (lvl - 1)) >> 1LL);
}
struct Node{
	int cnt, lc, rc;
	Node(){
		this->lc = this->rc = -1;
	}	
};
vector<Node>st;
void build(int id, int l, int r){	
	st[id].cnt = r - l + 1;
	if(l == r){
		return;
	}
	int m = (l + r) >> 1;
	st.emplace_back(Node());
	build(st[id].lc = int(st.size()) - 1, l, m);
	st.emplace_back(Node());
	build(st[id].rc = int(st.size()) - 1, m + 1, r);
}
void update(int id, int C){
	int l = 1, r = n + 1;
	st[id].cnt--;
	while(l < r){
		int m = (l + r) >> 1;
		if(st[st[id].lc].cnt < C){
			C -= st[st[id].lc].cnt;
			st.emplace_back(st[st[id].rc]);
			st[id = st[id].rc = int(st.size()) - 1].cnt--;
			l = m + 1;
		}
		else{
			st.emplace_back(st[st[id].lc]);
			st[id = st[id].lc = int(st.size()) - 1].cnt--;
			r = m;
		}
	}
}
int walk(int id, int C){
	int l = 1, r = n + 1;
	while(l < r){
		int m = (l + r) >> 1;
		if(st[st[id].lc].cnt < C){
			C -= st[st[id].lc].cnt;
			id = st[id].rc;
			l = m + 1;
		}
		else{
			id = st[id].lc;
			r = m;
		}
	}
	return l;
}
int get(int id, int p){
	int ans = 0, l = 1, r = n + 1;
	while(l < r){
		int m = (l + r) >> 1;
		if(m < p){
			ans += st[st[id].lc].cnt;
			id = st[id].rc;
			l = m + 1;
		}	
		else{
			id = st[id].lc;
			r = m;
		}
	}
	return ans + st[id].cnt;
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> q >> t;
	st.assign(n + 2, Node());
	build(n + 1, 1, n + 1);
	vector<int>a(n);
	for(int& x : a){
		cin >> x;
	}
	for(int i = n - 1; i > -1; i--){
		st[i + 1] = st[i + 2];
		update(i + 1, level_id(a[i]) + 1);
	}
	ll z = 0, mod = (1LL * (n + 1) * (n + 2)) >> 1LL;
	for(int _ = 0; _ < q; _++){
		ll x, y;
		cin >> x >> y;
		if(t == 1){
			x = (x - 1 + z) % mod + 1;
			y = (y - 1 + z) % mod + 1;
		}
		int _x = walk(level(x), level_id(x)), _y = walk(level(y), level_id(y));
		if(_x == _y){
			cout << (z = min(x, y)) << "\n";
			continue;
		}
		int low = 2, high = n + 1, ans = 1;
		while(low <= high){
			int mid = (low + high) >> 1;
			if(get(mid, _x) == get(mid, _y)){
				low = (ans = mid) + 1;
			}
			else{
				high = mid - 1;
			}
		}
		cout << (z = ((1LL * ans * (ans - 1)) >> 1LL) + get(ans, _x)) << "\n";
	}
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:94:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60