#include <bits/extc++.h>
#include <bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmax(T &val, T nv) { return val < nv ? (val = nv, true) : false; }
template<class T> bool chmin(T &val, T nv) { return nv < val ? (val = nv, true) : false; }
using namespace std;
using ll = long long;
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
void kout(){ cerr << endl; }
template<class T1, class ...T2> void kout(T1 a, T2 ...e) { cerr << a << ' ', kout(e...); }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// What I should check
// 1. overflow
// 2. corner cases
// Enjoy the problem instead of hurrying to AC
// Good luck !
const int qry_t = 1, mody_t = 3, modx_t = 2, ad_t = 4;
const int MAX_N = 500010, MAX_Q = 1000010, inf = 1e9 + 7, QK = 20;
int m, q, W;
vector<pair<int,int>> dust;
pair<int,int> trans(int x, int y) {
return {x, W - y};
}
pair<int,int> trans(pair<int,int> d) {
return trans(d.first, d.second);
}
int cut[MAX_Q], cl;
int qt[MAX_Q + MAX_N], qid[MAX_Q + MAX_N], qL[MAX_Q + MAX_N], qx[MAX_Q + MAX_N], qy[MAX_Q + MAX_N];
pair<int,int> ans[MAX_Q + MAX_N];
#define priority_queue __gnu_pbds::priority_queue
namespace data {
struct cmpx { bool operator()(int a, int b) const { return dust[a].first > dust[b].first; } };
struct cmpy { bool operator()(int a, int b) const { return dust[a].second < dust[b].second; } };
// small comes out
//priority_queue<int, vector<int>, cmpx> linex[2 << QK];
priority_queue<int, cmpx> linex[2 << QK];
// big comes out
//priority_queue<int, vector<int>, cmpy> liney[2 << QK];
priority_queue<int, cmpy> liney[2 << QK];
int belong[MAX_Q + MAX_N];
priority_queue<int, cmpx>::point_iterator px[MAX_Q + MAX_N];
priority_queue<int, cmpy>::point_iterator py[MAX_Q + MAX_N];
pair<int,int> treeLR[2 << QK];
bool ok[MAX_N + MAX_Q];
vector<int> inside;
int cnt[2 << QK];
int create_dust(int x, int y) {
dust.pb(x, y);
return dust.size() - 1;
}
void putin(int sid, int tid) {
belong[sid] = tid;
px[sid] = linex[tid].push(sid);
py[sid] = liney[tid].push(sid);
}
void dfsclear(int L = 0, int R = cl - 1, int i = 1) {
if (cnt[i] == 0) return;
treeLR[i] = treeLR[0], cnt[i] = 0;
// priority_queue<int, vector<int>, cmpx>().swap(linex[i]);
// priority_queue<int, vector<int>, cmpy>().swap(liney[i]);
priority_queue<int, cmpx>().swap(linex[i]);
priority_queue<int, cmpy>().swap(liney[i]);
if (L == R) return;
int M = L + R >> 1;
dfsclear(L, M, i<<1), dfsclear(M+1, R, i<<1|1);
}
void init_tree() {
dfsclear();
for (int i : inside)
ok[i] = false, belong[i] = 0;
inside.clear();
}
// must be modified well already
void insertseg(int id, int L = 0, int R = cl - 1, int i = 1) {
if (L > R) return;
const auto &[l, r] = dust[id];
int M = L + R >> 1, mid = cut[ M ];
++cnt[i];
if (l <= mid && r >= mid) {
putin(id, i);
return;
}
if (L == R) {
belong[id] = 0;
return;
}
if (l < mid) insertseg(id, L, M, i << 1);
else insertseg(id, M+1, R, i << 1|1);
}
void addseg(int id) {
inside.pb(id);
ok[id] = true;
insertseg(id);
}
bool chmnmx(pair<int,int> &loc, int L, int R) {
return chmax(loc.first, L) || chmin(loc.second, R);
}
bool chmnmx(pair<int,int> &loc, pair<int,int> p) {
return chmnmx(loc, p.first, p.second);
}
pair<int,int> qry(int id) {
assert(ok[id]);
auto res = dust[id];
if (belong[id])
chmnmx(res, treeLR[belong[id]]);
return res;
}
void init_all() {
DE("cut");
debug(cut, cut + cl);
fill(treeLR, treeLR + (MAX_Q << 1), make_pair(0, inf));
}
void modiseg(int nL, int nR, int L = 0, int R = cl - 1, int i = 1) {
int M = L + R >> 1, mid = cut[ M ];
int P = nL == 0 ? nR : nL;
if ((P == nR && P >= mid) ||
(P == nL && P <= mid))
chmnmx(treeLR[i], nL, nR);
++cnt[i];
auto kill = [&](int id) {
linex[i].erase(px[id]);
liney[i].erase(py[id]);
};
if (nL > mid || nR < mid) {
DE("Modi ", nL, nR, P, cut[M], i);
// nL == 0 means that now is R bound
// need to take max y
vector<int> reinsert;
if (P == nL) {
auto &pq = liney[i];
while (pq.size()) {
if (dust[ pq.top() ].second < P) break;
int id = pq.top();
if (belong[id] != i) {
//assert(false);
pq.pop();
continue;
}
if (chmnmx(dust[id], treeLR[i])) {
liney[i].modify(py[id], id);
linex[i].modify(px[id], id);
continue;
}
assert(dust[id].first <= P && dust[id].second >= P);
chmax(dust[id].first, P);
kill(id);
reinsert.pb(id);
}
}
else {
assert(P < mid && P == nR);
auto &pq = linex[i];
while (pq.size()) {
if (dust[ pq.top() ].first > P) break;
int id = pq.top();
if (belong[id] != i) {
//assert(false);
pq.pop();
continue;
}
if (chmnmx(dust[id], treeLR[i])) {
liney[i].modify(py[id], id);
linex[i].modify(px[id], id);
continue;
}
assert(dust[id].first <= P && dust[id].second >= P);
chmin(dust[id].second, P);
kill(id);
reinsert.pb(id);
}
}
for (int id : reinsert)
insertseg(id, L, R, i);
}
if (L == R || P == mid) return;
if (P < mid)
modiseg(nL, nR, L, M, i<<1);
else
modiseg(nL, nR, M+1,R,i<<1|1);
}
void updateans(int qd) {
static int hcnt[MAX_N + MAX_Q];
int id = qid[qd];
if (ok[id]) {
assert(++hcnt[qd] == 1);
ans[qd] = qry(id);
}
}
}
void mody(int L) {
data::modiseg(0, L);
}
void modx(int L) {
data::modiseg(L, inf);
}
void cdqsolve(int L, int R) {
if (L == R) {
if (qt[L] == ad_t)
qid[L] = data::create_dust(qx[L], qy[L]);
return;
}
int M = L + R >> 1;
cdqsolve(L, M);
DE(L, M, R);
{
data::init_tree();
for (int i = L;i <= M;++i) if (qt[i] == ad_t) {
data::addseg(qid[i]);
}
for (int i = M+1;i <= R;++i) {
if (qt[i] == qry_t)
data::updateans(i);
if (qt[i] == modx_t)
modx(qL[i]);
if (qt[i] == mody_t)
mody(qL[i]);
}
for (int i = L;i <= M;++i) if (qt[i] == ad_t)
dust[ qid[i] ] = data::qry(qid[i]);
}
cdqsolve(M+1, R);
}
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> W >> m >> q;
if (m > 2000) return 1;
for (int i = 0;i < m;++i) {
qt[i] = ad_t;
cin >> qx[i] >> qy[i];
tie(qx[i], qy[i]) = trans(qx[i], qy[i]);
qid[i] = i;
}
for (int i = m, t;i < m + q;++i) {
cin >> qt[i]; t = qt[i];
// qry dust id
if (t == qry_t) {
cin >> qid[i]; --qid[i];
}
if (t == mody_t || t == modx_t){
cin >> qL[i];
if (t == modx_t) qL[i] = W - qL[i];
cut[cl++] = qL[i];
}
// add dust
if (t == 4) {
cin >> qx[i] >> qy[i];
tie(qx[i], qy[i]) = trans(qx[i], qy[i]);
}
}
sort(cut, cut + cl);
cl = unique(cut, cut + cl) - cut;
chmax(cl, 1);
data::init_all();
cdqsolve(0, m + q - 1);
for (int i = m;i < m + q;++i) {
if (qt[i] == qry_t) {
ans[i] = trans(ans[i]);
auto [x, y] = ans[i];
cout << x << ' ' << y << '\n';
}
}
}
Compilation message
sweeping.cpp: In function 'void data::dfsclear(int, int, int)':
sweeping.cpp:89:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
89 | int M = L + R >> 1;
| ~~^~~
sweeping.cpp: In function 'void data::insertseg(int, int, int, int)':
sweeping.cpp:105:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
105 | int M = L + R >> 1, mid = cut[ M ];
| ~~^~~
sweeping.cpp: In function 'void data::init_all()':
sweeping.cpp:15:17: warning: statement has no effect [-Wunused-value]
15 | #define DE(...) 0
| ^
sweeping.cpp:144:3: note: in expansion of macro 'DE'
144 | DE("cut");
| ^~
sweeping.cpp:16:20: warning: statement has no effect [-Wunused-value]
16 | #define debug(...) 0
| ^
sweeping.cpp:145:3: note: in expansion of macro 'debug'
145 | debug(cut, cut + cl);
| ^~~~~
sweeping.cpp: In function 'void data::modiseg(int, int, int, int, int)':
sweeping.cpp:150:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
150 | int M = L + R >> 1, mid = cut[ M ];
| ~~^~~
sweeping.cpp:15:17: warning: statement has no effect [-Wunused-value]
15 | #define DE(...) 0
| ^
sweeping.cpp:166:3: note: in expansion of macro 'DE'
166 | DE("Modi ", nL, nR, P, cut[M], i);
| ^~
sweeping.cpp: In function 'void cdqsolve(int, int)':
sweeping.cpp:258:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
258 | int M = L + R >> 1;
| ~~^~~
sweeping.cpp:15:17: warning: statement has no effect [-Wunused-value]
15 | #define DE(...) 0
| ^
sweeping.cpp:262:2: note: in expansion of macro 'DE'
262 | DE(L, M, R);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
126 ms |
138604 KB |
Output is correct |
| 2 |
Incorrect |
104 ms |
138348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
85 ms |
122348 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
88 ms |
122348 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
88 ms |
122348 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
126 ms |
138604 KB |
Output is correct |
| 2 |
Incorrect |
104 ms |
138348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
