#define local
#ifndef local
#include ""
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 1500005 + 5;
const int oo = 1e9 + 7, mod = 1e9 + 7;
mt19937 rng(1);
int rnd(int l, int r){
int temp = rng() % (r - l + 1);
return abs(temp) + l;
}
int n, m, q;
int x[N], y[N];
int type[N], width[N];
ii answer[N];
vector<ii> asks[N];// ask which node, after which query?
vector<int> queries[N];// queries like "we start from query i, we ask for this node"
set<int> IT1[(2LL << 21)], IT2[(2LL << 21)];
void upd1(int id, int l, int r, int pos, int val, bool add){
if(add) IT1[id].insert(val);
else IT1[id].erase(val);
if(l == r) return;
int mid = (l + r) >> 1;
if(pos <= mid) upd1(id << 1, l, mid, pos, val, add);
else upd1(id << 1 | 1, mid + 1, r, pos, val, add);
}
int get1(int id, int l, int r, int le, int ri){
if(IT1[id].size() == 0) return oo;
if(l == r){
int temp = (*IT1[id].begin());
if(temp > ri || temp < le) return oo;
return l;
}
// cout << "ID " << id << " ";
// for(auto it : IT1[id]) cout << it << " ";
// cout << "\n";
int mid = (l + r) >> 1;
if(!IT1[id << 1].size()) return get1(id << 1 | 1, mid + 1, r, le, ri);
else{
set<int>::iterator it = IT1[id << 1].lower_bound(le);
if(it == IT1[id << 1].end() || (*it) > ri) return get1(id << 1 | 1, mid + 1, r, le, ri);
else return get1(id << 1, l, mid, le, ri);
}
}
void upd2(int id, int l, int r, int pos, int val, bool add){
if(add) IT2[id].insert(val);
else IT2[id].erase(val);
if(l == r) return;
int mid = (l + r) >> 1;
if(pos <= mid) upd2(id << 1, l, mid, pos, val, add);
else upd2(id << 1 | 1, mid + 1, r, pos, val, add);
}
int get2(int id, int l, int r, int le, int ri){
if(IT2[id].size() == 0) return oo;
if(l == r){
int temp = (*IT2[id].begin());
if(temp > ri || temp < le) return oo;
return l;
}
int mid = (l + r) >> 1;
if(!IT2[id << 1].size()) return get2(id << 1 | 1, mid + 1, r, le, ri);
else{
set<int>::iterator it = IT2[id << 1].lower_bound(le);
if(it == IT2[id << 1].end() || (*it) > ri) return get2(id << 1 | 1, mid + 1, r, le, ri);
else return get2(id << 1, l, mid, le, ri);
}
}
vector<int> v1, v2;
#ifdef local
void process(){
cin >> n >> m >> q;
for(int i = 1; i <= m; i++){
cin >> x[i] >> y[i];
queries[1].pb(i);
}
int cnt1 = m, cnt2 = 0, cnt3 = 0;
for(int i = 1; i <= q; i++){
int typ;
cin >> typ;
if(typ == 1){
int x;
cin >> x;
cnt3++;
asks[x].pb({cnt2, cnt3});
}
else if(typ == 2){
cnt2++;
int l;
cin >> l;
type[cnt2] = 0, width[cnt2] = l;
}
else if(typ == 3){
cnt2++;
int l;
cin >> l;
type[cnt2] = 1, width[cnt2] = l;
}
else{
cnt1++;
cin >> x[cnt1] >> y[cnt1];
queries[cnt2 + 1].pb(cnt1);
}
}
for(int i = 1; i <= cnt1; i++) reverse(asks[i].begin(), asks[i].end());
int cnth = 0, cntv = 0;
for(int i = 1; i <= cnt2; i++){
if(type[i] == 0) cnth++;
else cntv++;
}
int temph = cnth, tempv = cntv;
cnth = 0, cntv = 0;
v1.pb(-1), v2.pb(-1);
for(int i = 1; i <= cnt2; i++){
if(type[i] == 0){
cnth++;
// cout << "OKOKOK " << width[i] << "\n";
upd1(1, 1, temph, cnth, width[i], 1);
v1.pb(i);
}
else{
cntv++;
upd2(1, 1, tempv, cntv, width[i], 1);
v2.pb(i);
}
}
v1.pb(oo), v2.pb(oo);
//return;
cnth = 0, cntv = 0;
for(int i = 1; i <= cnt2; i++){
for(auto it : queries[i]){
int pos = it, pos1 = oo, pos2 = oo;
// H first: given current (x, y)
int le = y[pos], ri = n - x[pos] - 1;
if(le <= ri) pos1 = get1(1, 1, temph, le, ri);
// cout << le << " " << ri << "\n";
le = x[pos], ri = n - y[pos] - 1;
if(le <= ri) pos2 = get2(1, 1, tempv, le, ri);
// cout << le << " " << ri << "\n";
// continue;
pos1 = v1[min((int)v1.size() - 1, pos1)], pos2 = v2[min((int)v2.size() - 1, pos2)];
// cout << i << " " << pos << " " << pos1 << " " << pos2 << "\n";
while(asks[pos].size() && asks[pos].back().fi < min(pos1, pos2)){
// cout << "OK " << asks[pos].back().fi << " " << asks[pos].back().se << "\n";
answer[asks[pos].back().se] = make_pair(x[pos], y[pos]);
asks[pos].pop_back();
}
if(min(pos1, pos2) > cnt2) continue;
// cout << pos1 << " " << pos2 << "\n";
// continue;
if(pos1 < pos2) x[pos] = n - width[pos1];
else y[pos] = n - width[pos2];
// cout << pos1 << " " << pos2 << "\n";
// continue;
queries[min(pos1, pos2) + 1].pb(it);
}
if(type[i] == 0){
cnth++;
upd1(1, 1, temph, cnth, width[i], 0);
}
else{
cntv++;
upd2(1, 1, temph, cntv, width[i], 0);
}
}
for(int i = 1; i <= cnt1; i++){
for(auto it : asks[i]) answer[it.se] = {x[i], y[i]};
}
for(int i = 1; i <= cnt3; i++) cout << answer[i].fi << " " << answer[i].se << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
process();
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
576 ms |
943852 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12256 ms |
903452 KB |
Output is correct |
| 2 |
Correct |
12068 ms |
903576 KB |
Output is correct |
| 3 |
Correct |
10683 ms |
903716 KB |
Output is correct |
| 4 |
Incorrect |
6922 ms |
902732 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12637 ms |
978996 KB |
Output is correct |
| 2 |
Correct |
10846 ms |
966328 KB |
Output is correct |
| 3 |
Correct |
3809 ms |
954740 KB |
Output is correct |
| 4 |
Execution timed out |
18080 ms |
987308 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12637 ms |
978996 KB |
Output is correct |
| 2 |
Correct |
10846 ms |
966328 KB |
Output is correct |
| 3 |
Correct |
3809 ms |
954740 KB |
Output is correct |
| 4 |
Execution timed out |
18080 ms |
987308 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
576 ms |
943852 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
