| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1079751 |
2024-08-29T00:39:00 Z |
ainta |
Sweeping (JOI20_sweeping) |
C++17 |
|
8499 ms |
525988 KB |
#include <bits/stdc++.h>
using namespace std;
#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define rep(i,b) rng(i,0,b-1)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
#define per(i,b) gnr(i,b-1,0)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
typedef long long ll;
using pii=pair<int,int>;
using vi=vc<int>;
using uint=unsigned;
using ull=unsigned long long;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using t3=tuple<int,int,int>;
ll rand_int(ll l, ll r) { //[l, r]
#ifdef LOCAL
static mt19937_64 gen;
#else
static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
#endif
return uniform_int_distribution<ll>(l, r)(gen);
}
template <uint MD> struct ModInt {
using M = ModInt;
const static M G;
uint v;
ModInt(ll _v = 0) { set_v(_v % MD + MD); }
M& set_v(uint _v) {
v = (_v < MD) ? _v : _v - MD;
return *this;
}
explicit operator bool() const { return v != 0; }
M operator-() const { return M() - *this; }
M operator+(const M& r) const { return M().set_v(v + r.v); }
M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
M operator*(const M& r) const { return M().set_v(ull(v) * r.v % MD); }
M operator/(const M& r) const { return *this * r.inv(); }
M& operator+=(const M& r) { return *this = *this + r; }
M& operator-=(const M& r) { return *this = *this - r; }
M& operator*=(const M& r) { return *this = *this * r; }
M& operator/=(const M& r) { return *this = *this / r; }
bool operator==(const M& r) const { return v == r.v; }
M pow(ll n) const {
M x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
M inv() const { return pow(MD - 2); }
friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
using Mint = ModInt<1000000007>;
template<> const Mint Mint::G = Mint(3);
#define N_ 1501000
struct Query{
int type;
int p, l;
int x, y;
}U[N_];
pii Ans[N_];
pii w[N_];
int L, Cur[N_];
priority_queue<pii, vector<pii> ,greater<pii> >PQX[N_], PQY[N_];
priority_queue<pii >PQX2[N_], PQY2[N_];
int MX[N_], MY[N_], Num[N_];
void DnC(int b, int e){
if(b==e){
if(U[b].type == 4){
w[b] = {U[b].x,U[b].y};
}
return;
}
int m = (b+e)>>1;
DnC(b,m);
DnC(m+1,e);
int cnt = 1;
MX[1]=MY[1]=0;
auto Put = [&](int nd, int idx){
PQX[nd].push({w[idx].fi,idx});
PQX2[nd].push({w[idx].fi,idx});
PQY[nd].push({w[idx].se,idx});
PQY2[nd].push({w[idx].se,idx});
Num[idx] = nd;
};
rng(i,b,m){
if(U[i].type == 4){
Cur[i]=1;
Put(cnt, i);
Num[i] = cnt;
}
}
set<int>SX;
SX.insert(0);
SX.insert(L+1);
map<int,int>SM;
SM[0] = 1;
rng(i,m+1,e){
if(U[i].type==1){
int p = U[i].p;
if(Cur[p]){
Ans[i] = {max(w[p].fi, MX[Num[p]]), max(w[p].se, MY[Num[p]])};
}
}
if(U[i].type==2){ // x < L-l && y <=l -> (L-l, y)
int l = U[i].l;
if(SX.find(L-l) != SX.end())continue;
auto it2 = SX.lower_bound(L-l);
auto it1 = prev(it2);
int bx = *it1, ex = *it2;
int nd = SM[*it1];
vi Z1,Z2;
int CK=0;
while(1){
while(!PQY[nd].empty()){
auto [y1, idx1] = PQY[nd].top();
if(Num[idx1] != nd){
PQY[nd].pop();
continue;
}
if(y1 > l){
cnt++;
SX.insert(L-l);
SM[L-l] = cnt;
MX[cnt] = L-l;
MY[cnt] = MY[nd];
for(auto &idx : Z1){
Put(cnt, idx);
}
for(auto &idx : Z2){
PQY2[nd].push({w[idx].se,idx});
}
CK=1;
break;
}
Z1.pb(idx1);
PQY[nd].pop();
break;
}
if(CK)break;
while(!PQY2[nd].empty()){
auto [y2, idx2] = PQY2[nd].top();
if(Num[idx2] != nd){
PQY2[nd].pop();
continue;
}
if(y2 <= l){
cnt++;
SX.insert(L-l);
SM[L-l] = nd;
SM[bx] = cnt;
MX[cnt] = MX[nd];
MY[cnt] = MY[nd];
MX[nd] = L-l;
for(auto &idx : Z2){
Put(cnt, idx);
}
for(auto &idx : Z1){
PQY[nd].push({w[idx].se,idx});
}
CK=1;
break;
}
Z2.pb(idx2);
PQY2[nd].pop();
break;
}
if(CK || (PQY[nd].empty() && PQY2[nd].empty()))break;
}
}
if(U[i].type==3){
}
}
rng(i,1,cnt){
while(!PQX[i].empty())PQX[i].pop();
while(!PQX2[i].empty())PQX2[i].pop();
while(!PQY[i].empty())PQY[i].pop();
while(!PQY2[i].empty())PQY2[i].pop();
}
rng(i,b,m){
if(U[i].type == 4){
w[i].fi = max(w[i].fi, MX[Num[i]]);
w[i].se = max(w[i].se, MY[Num[i]]);
Cur[i]=0;
}
}
}
int RN[N_];
void Solve(){
int m, Q;
scanf("%d%d%d",&L,&m,&Q);
rng(i,1,m){
scanf("%d%d",&U[i].x,&U[i].y);
U[i].type = 4;
RN[i]=i;
}
int cc = m;
rng(i,m+1,m+Q){
scanf("%d",&U[i].type);
if(U[i].type == 1){
scanf("%d",&U[i].p);
U[i].p = RN[U[i].p];
}
if(U[i].type == 2){
scanf("%d",&U[i].l);
}
if(U[i].type == 3){
scanf("%d",&U[i].l);
}
if(U[i].type == 4){
RN[++cc] = i;
scanf("%d%d",&U[i].x,&U[i].y);
}
}
DnC(1,m+Q);
rng(i,1,m+Q){
if(U[i].type==1)printf("%d %d\n",Ans[i].fi,Ans[i].se);
}
}
int main(){
int TC=1;
//scanf("%d",&TC);
while(TC--){
Solve();
}
}
Compilation message
sweeping.cpp: In function 'void DnC(int, int)':
sweeping.cpp:136:28: warning: unused variable 'ex' [-Wunused-variable]
136 | int bx = *it1, ex = *it2;
| ^~
sweeping.cpp: In function 'void Solve()':
sweeping.cpp:223:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
223 | scanf("%d%d%d",&L,&m,&Q);
| ~~~~~^~~~~~~~~~~~~~~~~~~
sweeping.cpp:225:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
225 | scanf("%d%d",&U[i].x,&U[i].y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:231:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
231 | scanf("%d",&U[i].type);
| ~~~~~^~~~~~~~~~~~~~~~~
sweeping.cpp:233:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
233 | scanf("%d",&U[i].p);
| ~~~~~^~~~~~~~~~~~~~
sweeping.cpp:237:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
237 | scanf("%d",&U[i].l);
| ~~~~~^~~~~~~~~~~~~~
sweeping.cpp:240:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
240 | scanf("%d",&U[i].l);
| ~~~~~^~~~~~~~~~~~~~
sweeping.cpp:244:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
244 | scanf("%d%d",&U[i].x,&U[i].y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
85 ms |
189008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8499 ms |
512064 KB |
Output is correct |
| 2 |
Correct |
8478 ms |
525988 KB |
Output is correct |
| 3 |
Correct |
8294 ms |
519004 KB |
Output is correct |
| 4 |
Correct |
3880 ms |
366148 KB |
Output is correct |
| 5 |
Correct |
4100 ms |
365412 KB |
Output is correct |
| 6 |
Correct |
6642 ms |
510268 KB |
Output is correct |
| 7 |
Correct |
7924 ms |
508856 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4761 ms |
476300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4761 ms |
476300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
85 ms |
189008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
