oj.uz

답안 #259919

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
259919 2020-08-08T19:40:47 Z shayan_p 청소 (JOI20_sweeping) C++17
64 / 100
 9883 ms 110684 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;
typedef pair<pii, pii> pi4;

const int maxn = 2e6 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

struct node{
    node *L, *R;
    int sz;
    pi4 val;
    pii mn;
    node(pi4 _val){
	L = R = 0, sz = 1;
	val =_val;
	mn = {val.S.F + val.S.S, val.F.F};
    }
};
void bld(node* a){
    a->sz = (a->L ? a->L->sz : 0) + (a->R ? a->R->sz : 0) + 1;
    a->mn = min({ a->L ? a->L->mn : (pii){inf, inf}, a->R ? a->R->mn : (pii){inf, inf}, (pii){a->val.S.F + a->val.S.S, a->val.F.F} });
}
node* merge(node* a, node* b){
    if(!a)
	return b;
    if(!b)
	return a;
    if( ( rand() % ((a->sz) + (b->sz)) ) < (a->sz) ){
 	a->R = merge(a->R, b);
	bld(a);
	return a;
    }
    else{
	b->L = merge(a, b->L);
	bld(b);
	return b;
    }
}
pair<node*, node*> split(node *rt, int x){
    if(!rt)
	return {0, 0};
    if(rt->val.F.F >= x){
	auto p = split(rt->L, x);
	rt->L = p.S;
	bld(rt);
	return {p.F, rt};
    }
    else{
	auto p = split(rt->R, x);
	rt->R = p.F;
	bld(rt);
	return {rt, p.S};
    }
}
void print(node *rt){
    if(!rt)
	return;
    print(rt->L);
    cout << "[ "<< (rt->val.F.F) << " " << rt->val.F.S << "  " << rt->mn.F << "  " << rt->mn.S << "] "<< " ";
    print(rt->R);
}

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;
    node* rt;
    
    void restart(){
	mp.clear();
	rt = 0;
	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;
	auto [A, B] = split(rt, L);
	auto [C, D] = split(B, R);
	
	pii ans = mp.lower_bound( {C->mn.S, -1} )->F;
	rt = merge(A, merge(C, D));
	return ans;
    }
    void ins(pii a, pii b){
	assert(mp.count(a) == 0);	
	mp[a] = b;
	auto [A, B] = split(rt, a.F);
	rt = merge(A, merge(new node({a, b}), B));
    }
    void era(pii a){
	mp.erase(a);
	auto [A, B] = split(rt, a.F);
	auto [C, D] = split(B, a.F + 1);	
	assert(C);	
	rt = merge(A, D);
    }
    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)};
    }
};

const int Log = 22;

//bigTraingle tr[Log];
//vector<int> ids[Log];
//int who[maxn];
bigTraingle tr;

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

    srand(time(0));
    
    int m, q;
    cin >> N >> m >> q;
 
    vector<pii> p;
    /*    for(int i = 0; i < Log; 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});
	    }
	}
	}*/

    tr.restart();
    for(int i = 0; i < m; i++){
	int x, y;
	cin >> x >> y;
	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]);
	    pii ans = tr.calc(p[id]);


	    
	    cout << ans.F << " " << ans.S << "\n";
	}
	if(task == 2){
	    int l;
	    cin >> l;
	    /*	    for(int i = 0; i < Log; i++)
		if(!ids[i].empty())
		tr[i].add(l, 1);*/
	    tr.add(l, 1);
	    
	}
	if(task == 3){
	    int l;
	    cin >> l;
	    /*  for(int i = 0; i < Log; i++)
		if(!ids[i].empty())
		tr[i].add(l, 0);*/
	    tr.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;
		}*/
	    assert(0);
	}	
    }
    return 0;
}

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 512 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 163 ms 8708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8830 ms 110604 KB Output is correct
2 Correct 9025 ms 110304 KB Output is correct
3 Correct 6736 ms 109664 KB Output is correct
4 Correct 6429 ms 110188 KB Output is correct
5 Correct 9231 ms 110176 KB Output is correct
6 Correct 9554 ms 110176 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8830 ms 110604 KB Output is correct
2 Correct 9025 ms 110304 KB Output is correct
3 Correct 6736 ms 109664 KB Output is correct
4 Correct 6429 ms 110188 KB Output is correct
5 Correct 9231 ms 110176 KB Output is correct
6 Correct 9554 ms 110176 KB Output is correct
7 Correct 8296 ms 110484 KB Output is correct
8 Correct 8547 ms 110684 KB Output is correct
9 Correct 7993 ms 110220 KB Output is correct
10 Correct 6921 ms 109920 KB Output is correct
11 Correct 6399 ms 110304 KB Output is correct
12 Correct 9434 ms 110480 KB Output is correct
13 Correct 9529 ms 110448 KB Output is correct
14 Correct 509 ms 66296 KB Output is correct
15 Correct 627 ms 22500 KB Output is correct
16 Correct 8318 ms 110684 KB Output is correct
17 Correct 9883 ms 110320 KB Output is correct

Subtask #5
0 / 25.0

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