제출 #260133

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
260133		shayan_p	청소 (JOI20_sweeping)	C++14	100 / 100	7214 ms	367644 KiB

sweeping

// And you curse yourself for things you never done
 
#include<bits/stdc++.h>
 
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii, pii> pi4;
 
const int maxn = 2e6 + 10, mod = 1e9 + 7, inf = 1e9 + 10;
  
int N;
 
pii trans(pii p){ // x1 x2
    return {p.S, N - p.F};
}
pii trans2(pii p){ // x1 x2
    return {p.F, N - p.S};
}
 
struct bigTraingle{
    map<pii, pii> mp;
    vector<pair<pii, int> > v;
    int sp[21][maxn];
    void restart(){
	mp.clear();
	mp[{0, N}] = {0, 0};
    }
    pii color(pii p){
	int L = upper_bound(v.begin(), v.end(), (pair<pii, int>){{p.F, inf}, inf}) - v.begin() - 1;
	int R = upper_bound(v.begin(), v.end(), (pair<pii, int>){{N - p.S, inf}, inf}) - v.begin();
	assert(L < R);
	int lg = 31 - __builtin_clz(R-L);
	int A = sp[lg][L], B = sp[lg][R - (1<<lg)];
	if(v[B].S < v[A].S)
	    A = B;
	return v[A].F;
    }
    void add(int l, bool is){
	int x = l, y = N - l;
	if(is)
	    swap(x, y);
	auto it = --mp.upper_bound({x, inf});
	int L = it->F.F, R = it->F.S;
	pii p = it->S;
	mp.erase(it);
	if(!is){
	    pii A = {L, x}, B = {x + 1, R};
	    mp[A] = p;
	    if(B.F <= B.S)
		mp[B] = {B.F, p.S};
	}
	else{
	    pii A = {L, x - 1}, B = {x, R};
	    mp[B] = p;
	    if(A.F <= A.S)
		mp[A] = {p.F, N - A.S};
	}
    }
    pii calc(pii p){
	pii s = color(p);
	pii C = trans2(s);
	return {max(C.F, p.F), max(C.S, p.S)};
    }
    void prepare(){
	v.clear();
	for(auto x : mp){
	    v.PB({x.F, x.S.F + x.S.S});
	}
	assert(sz(v));
	int Log = 31 - __builtin_clz(sz(v));
	for(int i = 0; i < sz(v); i++)
	    sp[0][i] = i;
	for(int i = 1; i <= Log; i++){
	    for(int j = 0; j < sz(v); j++){
		sp[i][j] = sp[i-1][j];
		int k = j + (1<<(i-1));		
		if(k < sz(v) && v[sp[i-1][j]].S > v[sp[i-1][k]].S)
		    sp[i][j] = sp[i-1][k];
	    }
	}
    }
};

int prog[maxn]; //////to Del

int LST[maxn];
vector<pii> conf, p, tell[maxn];
pii ans[maxn];

vector<int> tdo[4 * maxn];

void place(int f, int s, int x, int l = 0, int r = sz(conf) + 1, int id = 1){
    if(f >= s || s <= l || r <= f)
	return;
    if(f <= l && r <= s){
	tdo[id].PB(x);
	return;
    }
    int mid = (l+r) >> 1;
    place(f, s, x, l, mid, 2*id);
    place(f, s, x, mid, r, 2*id+1);    
}

bigTraingle tr;

void solve(int l = 0, int r = sz(conf) + 1, int id = 1){
    if(r-l == 1){
	for(pii x : tell[l]){
	    assert(prog[x.F] == l);	    
	    ans[x.S] = p[x.F];
	}
    }
    if(r-l > 1){
	int mid = (l+r) >> 1;
	solve(l, mid, 2*id);
	solve(mid, r, 2*id + 1);
    }
    if(r == sz(conf) + 1)
	assert(tdo[id].empty());
    if(tdo[id].empty())
	return;
    tr.restart();
    for(int i = l; i < r; i++)
	tr.add(conf[i].F, conf[i].S);
    tr.prepare();
    for(int i : tdo[id]){
	assert(prog[i] == l);
	prog[i] = r;
	p[i] = tr.calc(p[i]);
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();
 
    int m, q;
    cin >> N >> m >> q;    
    p.resize(m);
    for(int i = 0; i < m; i++){
	cin >> p[i].F >> p[i].S;
    }
    vector<pair<pii, int> > seg;
    int Q = 0;
    for(int i = 0; i < q; i++){
	int task;
	cin >> task;
	if(task == 1){
	    int id;
	    cin >> id;
	    --id;
	    tell[sz(conf)].PB({id, Q++});
	    seg.PB({{LST[id], sz(conf)}, id});
	    LST[id] = sz(conf);
	}
	if(task == 2){
	    int l;
	    cin >> l;
	    conf.PB({l, 1});
	}
	if(task == 3){
	    int l;
	    cin >> l;
	    conf.PB({l, 0});
	}
	if(task == 4){
	    int x, y;
	    cin >> x >> y;
	    LST[sz(p)] = sz(conf);



	    prog[sz(p)] = sz(conf);

	    
	    p.PB({x, y});
	}	
    }
    for(auto x : seg){
	place(x.F.F, x.F.S, x.S);
    }
    solve();
    for(int i = 0; i < Q; i++){
	cout << ans[i].F << " " << ans[i].S << "\n";
    }
    return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25