oj.uz

답안 #259775

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
259775 2020-08-08T13:52:16 Z shayan_p 청소 (JOI20_sweeping) C++14
0 / 100
 18000 ms 22928 KB 
// 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;
/*

struct node{
    node *L, *R;
    int mx;
    node(){
	L = R = 0;
	mx = -1;
    }
    void add(int f, int s, int x, int l = 0, int r = inf){
	if(f <= l && r <= s){
	    mx = max(mx, x);
	    return;
	}
	int mid = (l+r) >> 1;
	if(s > l && mid > f){
	    if(L == 0)
		L = new node();
	    L->add(f, s, x, l, mid);
	}
	if(s > mid && r > f){
	    if(R == 0)
		R = new node();
	    R->add(f, s, x, mid, r);
	}
    }
    int ask(int pos, int l = 0, int r = inf){
	int mid = (l+r) >> 1;
	if(pos < mid){
	    if(L == 0)
		return mx;
	    return max(mx, L->ask(pos, l, mid));
	}
	else{
	    if(R == 0)
		return mx;
	    return max(mx, R->ask(pos, mid, r));
	}
    }    
};node* emp;
struct node2{
    node2 *L, *R;
    node* s;
    node2(){
	L = R = 0;
	s = 0;
    }
    void add(int fx, int sx, int fy, int sy, int x, int l = 0, int r = inf){
	if(fx <= l && r <= sx){
	    if(s == 0)
		s = new node();
	    s->add(fy, sy, x);
	    return;
	}
	int mid = (l+r) >> 1;
	if(sx > l && mid > fx){
	    if(L == 0)
		L = new node2();
	    L->add(fx, sx, fy, sy, x, l, mid);
	}
	if(sx > mid && r > fx){
	    if(R == 0)
		R = new node2();
	    R->add(fx, sx, fy, sy, x, mid, r);
	}
    }
    int ask(int posx, int posy, int l = 0, int r = inf){
	int mid = (l+r) >> 1;
	if(posx < mid){
	    int ans = -1;
	    if(s)
		ans = s->ask(posy);
	    if(L)
		ans = max(ans, L->ask(posx, posy, l, mid));
	    return ans;
	}
	else{
	    int ans = -1;
	    if(s)
		ans = s->ask(posy);
	    if(R)
		ans = max(ans, R->ask(posx, posy, mid, r));
	    return ans;
	}
    }
};node2* emp2;
*/


struct node2{
    vector<pii> X, Y;
    vector<int> val;
    void add(int fx, int sx, int fy, int sy, int x){
	val.PB(x);
	X.PB({fx, sx});
	Y.PB({fy, sy});
    }
    int ask(int posx, int posy){
	int ans = -1;
	for(int i = 0; i < sz(val); i++){
	    if(X[i].F <= posx && posx < X[i].S && Y[i].F <= posy && posy < Y[i].S)
		ans = max(ans, val[i]);
	}
	return ans;
    }
};
    
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<pii> to;
    node2* rt;
    
    void restart(){
	mp.clear();
	to.clear();
	rt = new node2();
	ins({0, N}, {0, 0});
    }
    pii color(pii p){
	int c = rt->ask(p.F, p.S);
	return to[c];
    }
    void put(pii l, pii r, pii x){
	rt->add(l.F, r.F + 1, l.S, r.S + 1, sz(to));
	to.PB(x);	
    }
    void ins(pii a, pii b){
	mp[a] = b;
	put(b, trans(a), a);
    }
    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};
	    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;

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.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 162 ms 11368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 18066 ms 22928 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 18066 ms 22928 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -