Submission #259754

#	Time	Username	Problem	Language	Result	Execution time	Memory
259754		shayan_p	Sweeping (JOI20_sweeping)	C++14	0 / 100	18008 ms	19912 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 bigTraingle{
    map<pii, pii> mp;
    void restart(){
	mp.clear();
	mp[{0, N}] = {0, 0};
    }
    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){
	for(auto it : mp){
	    pii A = it.S, B = trans(it.F), C = trans2(it.F);
	    if(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)};
	    }		
	}
	assert(0);
    }
};bigTraingle tr;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int m, q;
    cin >> N >> m >> q;

    vector<pii> p(m);
    for(int i = 0; i < m; i++){
	cin >> p[i].F >> p[i].S;
    }
    tr.restart();
    while(q--){
	int task;
	cin >> task;
	if(task == 1){
	    int id;
	    cin >> id;
	    pii ans = tr.calc(p[--id]);
	    cout << ans.F << " " << ans.S << "\n";
	}
	if(task == 2){
	    int l;
	    cin >> l;
	    tr.add(l, 1);
	}
	if(task == 3){
	    int l;
	    cin >> l;
	    tr.add(l, 0);
	}
	if(task == 4){
	    //	    int x, y;
	    //  cin >> x >> y;
	    assert(0);
	}	
    }
    return 0;
}

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