oj.uz

답안 #259864

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
259864 2020-08-08T17:48:03 Z shayan_p 청소 (JOI20_sweeping) C++14
64 / 100
 14575 ms 571476 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;
    
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.0

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

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 174 ms 18712 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 14575 ms 571476 KB Output is correct
2 Correct 11259 ms 442600 KB Output is correct
3 Correct 8384 ms 424508 KB Output is correct
4 Correct 8216 ms 424908 KB Output is correct
5 Correct 13971 ms 424816 KB Output is correct
6 Correct 13484 ms 428964 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14575 ms 571476 KB Output is correct
2 Correct 11259 ms 442600 KB Output is correct
3 Correct 8384 ms 424508 KB Output is correct
4 Correct 8216 ms 424908 KB Output is correct
5 Correct 13971 ms 424816 KB Output is correct
6 Correct 13484 ms 428964 KB Output is correct
7 Correct 10967 ms 442688 KB Output is correct
8 Correct 11080 ms 442588 KB Output is correct
9 Correct 11235 ms 442608 KB Output is correct
10 Correct 9364 ms 424560 KB Output is correct
11 Correct 8764 ms 425048 KB Output is correct
12 Correct 13879 ms 428852 KB Output is correct
13 Correct 12807 ms 425092 KB Output is correct
14 Correct 283 ms 4216 KB Output is correct
15 Correct 857 ms 31300 KB Output is correct
16 Correct 14184 ms 554092 KB Output is correct
17 Correct 11662 ms 429068 KB Output is correct

Subtask #5
0 / 25.0

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