oj.uz

Submission #259915

# Submission time Handle Problem Language Result Execution time Memory
259915 2020-08-08T19:36:38 Z shayan_p Sweeping (JOI20_sweeping) C++17
1 / 100
 18000 ms 370044 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];
 
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});
	    }
	}
    }
    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 < Log; i++)
		if(!ids[i].empty())
		    tr[i].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);
	}
	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
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1528 KB Output is correct
2 Correct 27 ms 1784 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 25 ms 1536 KB Output is correct
5 Correct 49 ms 2808 KB Output is correct
6 Correct 6 ms 1152 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 18041 ms 353716 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 18073 ms 370044 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Execution timed out 18073 ms 370044 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1528 KB Output is correct
2 Correct 27 ms 1784 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 25 ms 1536 KB Output is correct
5 Correct 49 ms 2808 KB Output is correct
6 Correct 6 ms 1152 KB Output is correct
7 Execution timed out 18041 ms 353716 KB Time limit exceeded
8 Halted 0 ms 0 KB -