#pragma GCC optimize("unroll-loops,Ofast")
#define _GLIBCXX_DEBUG
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
//#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int maxn = 1.5e6+10;
const int inf = 1e9+69;
#define lc (v<<1)
#define rc (lc|1)
int vrt[maxn];
int trnum[maxn];
struct ltree
{
vector<int> vals; // min tree, sz = 2*n
vector<int> lazy;
vector<int> nid;
int n;
ltree()
{
n = 0;
}
inline void upd(int v)
{
if(v < n)
vals[v] = min(vals[lc], vals[rc]);
}
inline void put(int v, int x)
{
vals[v] = max(vals[v], x);
lazy[v] = max(lazy[v], x);
}
inline void shift(int v)
{
if(lazy[v] == 0) return;
if(v < n)
{
put(lc, lazy[v]);
put(rc, lazy[v]);
}
lazy[v] = 0;
}
inline void relax(int v)
{
stack<int> prs;
int x = v;
while(x > 0)
{
prs.push(x);
x >>= 1;
}
while(!prs.empty())
{
shift(prs.top());
prs.pop();
}
while(v > 0)
{
upd(v);
v >>= 1;
}
}
inline int get(int id)
{
relax(vrt[id]);
return vals[vrt[id]];
}
inline int get_min() // id
{
//if(n == 0)
// return inf;
int mn = vals[1];
int v = 1;
while(v < n)
{
if(vals[lc] == mn)
v = lc;
else
v = rc;
}
return nid[v];
}
inline void ass_max(int x)
{
put(1, x);
}
inline void add(int id, int x)
{
//n++;
if(n == 0)
{
vals = {-1, x};
lazy = {-1, 0};
nid = {-1, id};
n = 1;
vrt[id] = 1;
}
else
{
relax(n);
//
vals.push_back(vals[n]);
vals.push_back(x);
lazy.push_back(0);
lazy.push_back(0);
//
nid.push_back(nid[n]);
nid.push_back(id);
nid[n] = -1;
//
vrt[nid[2*n]] = 2*n;
vrt[nid[2*n+1]] = 2*n+1;
//
n++;
relax(n-1);
}
}
inline void remove(int id) // id should be in tree
{
if(n == 1)
{
vals = vector<int>();
lazy = vector<int>();
nid = vector<int>();
n = 0;
}
else
{
//cerr << "removing " << id << endl;
int v = vrt[id];
int x = 2*n-1;
relax(v);
relax(x);
//cerr << x << " " << v << " --- " << vals[0] << " " << vals[1] << " " << vals[2] << " " << vals[3] << endl;
//
swap(vals[v], vals[x]);
swap(nid[v], nid[x]);
vrt[nid[v]] = v;
vrt[nid[x]] = x;
//
vals[n-1] = vals[x-1];
nid[n-1] = nid[x-1];
vrt[nid[n-1]] = n-1;
//
vals.pop_back(); vals.pop_back();
lazy.pop_back(); lazy.pop_back();
nid.pop_back(); nid.pop_back();
//cerr << x << " " << v << " --- " << vals[0] << " " << vals[1] << endl;
//
n--;
relax(n-1);
if(v < 2*n)
relax(v);
//cerr << x << " " << v << " --- " << vals[0] << " " << vals[1] << " " << vals[2] << " " << vals[3] << endl;
}
}
} trees[maxn][2];
map<int, int> trid;
set<int> tempty;
bool pdone[maxn];
pii ppos[maxn];
#define X first
#define Y second
int H;
inline void add_tree(int id, pii pos, int v)
{
if(trid.find(v) == trid.end())
{
trid[v] = *tempty.begin();
tempty.erase(tempty.begin());
}
int x = trid[v];
trees[x][0].add(id*2, pos.X);
trees[x][1].add(id*2+1, pos.Y);
trnum[id] = x;
}
void add_seg(int x, int y, int h, int id, pii pos, int v)
{
int nx = x + h/2 + 1;
int ny = y + (h+1)/2 + 1;
if(h == 0)
{
//cerr << "ridim0" << endl;
}
if(h == 1)
{
if(pos.X == x and pos.Y == y)
add_tree(id, pos, v);
//else if(pos.X == x+1 and pos.Y == y)
// add_tree(id, pos, lc);
//else if(pos.X == x and pos.Y == y+1)
// add_tree(id, pos, rc);
else
cerr << "ridim" << endl;
//return;
}
if(pos.X >= nx)
{
add_seg(nx, y, (h+1)/2 - 1, id, pos, lc);
}
else if(pos.Y >= ny)
{
add_seg(x, ny, h/2 - 1, id, pos, rc);
}
else
{
//cerr << v << endl;
add_tree(id, pos, v);
}
}
inline void add_dust(int p, int x, int y)
{
if(x+y == H)
{
pdone[p] = true;
ppos[p] = pii(x, y);
}
else
{
add_seg(0, 0, H, p, pii(x, y), 1);
}
}
inline pii get_dust(int p)
{
if(pdone[p])
return ppos[p];
int x = trnum[p];
return pii(trees[x][0].get(p*2), trees[x][1].get(p*2+1));
}
inline void vert(int x, int y, int h, int l, int v)
{
if(l < 0) return;
if(trid.find(v) != trid.end())
{
int z = trid[v];
if( l >= (h/2) )
{
trees[z][1].ass_max(y+h-l);
}
else
{
while(trees[z][0].n > 0 and trees[z][0].vals[1] <= x+l)
{
int p = trees[z][0].get_min() / 2;
pii pos(trees[z][0].get(p*2), y+h-l);
trees[z][0].remove(p*2);
trees[z][1].remove(p*2+1);
//add_tree(p, pos, rc);
if(l == 0)
{
pdone[p] = true;
ppos[p] = pii(x, y+h);
}
else
{
add_dust(p, pos.X, pos.Y);
}
}
if(trees[z][0].n == 0)
{
tempty.insert(z);
trid.erase(v);
}
}
}
if( l > (h/2) )
{
vert(x + (h/2) + 1, y, ((h+1)/2)-1, l-h/2-1, lc);
}
if( l < (h/2) )
{
vert(x, y+(h+1)/2+1, h/2-1, l, rc);
}
}
inline void horz(int x, int y, int h, int l, int v)
{
if(l < 0) return;
if(trid.find(v) != trid.end())
{
int z = trid[v];
if( l >= (h+1)/2 )
{
trees[z][0].ass_max(x+h-l);
}
else
{
while(trees[z][1].n > 0 and trees[z][1].vals[1] <= y+l)
{
int p = trees[z][1].get_min() / 2;
pii pos(x+h-l, trees[z][1].get(p*2+1));
trees[z][0].remove(p*2);
trees[z][1].remove(p*2+1);
//add_tree(p, pos, lc);
if(l == 0)
{
pdone[p] = true;
ppos[p] = pii(x+h, y);
}
else
{
add_dust(p, pos.X, pos.Y);
}
}
if(trees[z][1].n == 0)
{
tempty.insert(z);
trid.erase(v);
}
}
}
if( l > (h+1)/2 )
{
horz(x, y+(h+1)/2+1, h/2-1, l-(h+1)/2-1, rc);
}
if( l < (h+1)/2 )
{
horz(x + (h/2) + 1, y, ((h+1)/2)-1, l, lc);
}
}
int32_t main()
{
ios::sync_with_stdio(false);
cin.tie(0);
//cerr << sizeof(vector<int>) << endl;
//cerr << sizeof(ltree) << endl;
vector<int> tmp(maxn);
iota(tmp.begin(), tmp.end(), 0);
tempty = set<int>(tmp.begin(), tmp.end());
int n, q; cin >> H >> n >> q;
for(int i = 0; i < n; i++)
{
//cerr << i << endl;
int x,y; cin >> x >> y;
add_dust(i, x, y);
}
int c = n;
while(q--)
{
int t; cin >> t;
if(t == 1)
{
int p; cin >> p;
p--;
pii ans = get_dust(p);
cout << ans.first << " " << ans.second << endl;
}
else if(t == 2)
{
int l; cin >> l;
//cerr << "horz " << 5-q << endl;
horz(0, 0, H, l, 1);
//for(int i = 0; i < c; i++)
//{
// pii p = get_dust(i);
// cerr << p.first << " " << p.second << endl;
//}
//cerr << "----" << endl;
}
else if(t == 3)
{
int l; cin >> l;
vert(0, 0, H, l, 1);
}
else // t == 4
{
int x,y; cin >> x >> y;
add_dust(c++, x, y);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18081 ms |
593808 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18084 ms |
737984 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18106 ms |
636784 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18106 ms |
636784 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18081 ms |
593808 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
