Submission #259864

#	Time	Username	Problem	Language	Result	Execution time	Memory
259864		shayan_p	Sweeping (JOI20_sweeping)	C++14	64 / 100	14575 ms	571476 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;
 
const int maxn = 1e6 + 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 node{
    node *L = 0, *R = 0;
    int val = inf;
};
node* rt = new node();

void put(int pos, int x, int l = 0, int r = N+1, node *nw = rt){
    if(r-l == 1){
	nw->val = x;
	return;
    }
    int mid = (l+r) >> 1;
    if(pos < mid){
	if(nw->L == 0)
	    nw->L = new node();
	put(pos, x, l, mid, nw->L);
    }
    else{
	if(nw->R == 0)
	    nw->R = new node();
	put(pos, x, mid, r, nw->R);
    }
    nw->val = min(nw->L ? nw->L->val : inf, nw->R ? nw->R->val : inf);
}
int best(int f, int s, int l = 0, int r = N+1, node* nw = rt){
    if(s <= l || r <= f)
	return inf;
    if(f <= l && r <= s)
	return nw->val;
    int mid = (l+r) >> 1;
    int ans = inf;
    if(nw->L)
	ans = min(ans, best(f, s, l, mid, nw->L));
    if(nw->R)
	ans = min(ans, best(f, s, mid, r, nw->R));
    return ans;
}
int choose(int f, int s, int x, int l = 0, int r = N+1, node* nw = rt){
    if(s <= l || r <= f || nw->val > x)
	return -1;
    if(r-l == 1)
	return l;
    if(f <= l && r <= s){
	int mid = (l+r) >> 1;
	if(nw->L && nw->L->val == x)
	    return choose(f, s, x, l, mid, nw->L);
	if(nw->R && nw->R->val == x)
	    return choose(f, s, x, mid, r, nw->R);
	assert(0);
    }
    int mid = (l+r) >> 1;
    int ans = -1;
    if(nw->L)
	ans = choose(f, s, x, l, mid, nw->L);
    if(ans != -1)
	return ans;
    if(nw->R)
	ans = choose(f, s, x, mid, r, nw->R);
    return ans;
}

struct bigTraingle{
    map<pii, pii> mp;
    
    void restart(){
	mp.clear();
	ins({0, N}, {0, 0});
    }
    pii color(pii p){
	auto IT1 = --mp.upper_bound({p.F, inf});
	auto IT2 = --mp.upper_bound({N - p.S, inf});
	int L = IT1->F.F, R = IT2->F.F + 1, val = best(L, R), pos = choose(L, R, val);
	return mp.lower_bound( {pos, -1} )->F;
	/*
	int num = N + 10;
	pii ans = {-1, -1};
	for(auto it = IT1; it != next(IT2); it++)
	    if(it->S.F + it->S.S < num)
		num = it->S.F + it->S.S, ans = it->F;
		return ans;*/
    }
    void ins(pii a, pii b){
	mp[a] = b;
	put(a.F, b.F + b.S);
    }
    void era(pii a){
	mp.erase(a);
	put(a.F, inf);
    }
    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;
	era(it->F);
	if(!is){
	    pii A = {L, x}, B = {x + 1, R};
	    ins(A, p);
	    if(B.F <= B.S)
		ins(B, {B.F, p.S});
	}
	else{
	    pii A = {L, x - 1}, B = {x, R};
	    ins(B, p);
	    if(A.F <= A.S)
		ins(A, {p.F, N - A.S});
	}
    }
    pii calc(pii p){
	pii s = color(p);
	pii A = mp[s], B = trans(s), C = trans2(s);
	assert(A.F <= p.F && A.S <= p.S && p.F <= B.F && p.S <= B.S);
	return {max(C.F, p.F), max(C.S, p.S)};
    }
};bigTraingle tr[20];
vector<int> ids[20];
int who[maxn];
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();
    
    int m, q;
    cin >> N >> m >> q;
 
    vector<pii> p;
    for(int i = 0; i < 20; i++){
	tr[i].restart();
	if(bit(m, i)){
	    for(int j = 0; j < (1<<i); j++){
		int x, y;
		cin >> x >> y;
		who[sz(p)] = i;
		ids[i].PB(sz(p));
		p.PB({x, y});
	    }
	}
    }
    while(q--){
	int task;
	cin >> task;
	if(task == 1){
	    int id;
	    cin >> id;
	    --id;
	    pii ans = tr[who[id]].calc(p[id]);
	    cout << ans.F << " " << ans.S << "\n";
	}
	if(task == 2){
	    int l;
	    cin >> l;
	    for(int i = 0; i < 20; i++)
		if(!ids[i].empty())
		    tr[i].add(l, 1);
	}
	if(task == 3){
	    int l;
	    cin >> l;
	    for(int i = 0; i < 20; i++)
		if(!ids[i].empty())
		    tr[i].add(l, 0);
	}
	if(task == 4){
	    int x, y;
	    cin >> x >> y;
 
	    vector<int> vv;
	    vv.PB(sz(p));
	    
	    p.PB({x, y});
	    int pt = 0;
	    while(!ids[pt].empty()){
		for(int x : ids[pt])
		    vv.PB(x), p[x] = tr[pt].calc(p[x]);		
		ids[pt].clear();
		tr[pt].restart();
		pt++;
	    }
	    swap(ids[pt], vv);
	    for(int x : ids[pt]){
		who[x] = pt;
	    }
	}	
    }
    return 0;
}

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