oj.uz

답안 #260127

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
260127 2020-08-09T11:04:57 Z shayan_p 청소 (JOI20_sweeping) C++14
1 / 100
 18000 ms 243064 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;
  
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<pair<pii, int> > v;
    int sp[21][maxn];
    void restart(){
	mp.clear();
	mp[{0, N}] = {0, 0};
    }
    pii color(pii p){
	int L = upper_bound(v.begin(), v.end(), (pair<pii, int>){{p.F, inf}, inf}) - v.begin() - 1;
	int R = upper_bound(v.begin(), v.end(), (pair<pii, int>){{N - p.S, inf}, inf}) - v.begin();
	assert(L < R);
	int lg = 31 - __builtin_clz(R-L);
	int A = sp[lg][L], B = sp[lg][R - (1<<lg)];
	if(v[B].S < v[A].S)
	    A = B;
	return v[A].F;
    }
    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){
	pii s = color(p);
	pii C = trans2(s);
	return {max(C.F, p.F), max(C.S, p.S)};
    }
    void prepare(){
	v.clear();
	for(auto x : mp){
	    v.PB({x.F, x.S.F + x.S.S});
	}
	assert(sz(v));
	int Log = 31 - __builtin_clz(sz(v));
	for(int i = 0; i < sz(v); i++)
	    sp[0][i] = i;
	for(int i = 1; i <= Log; i++){
	    for(int j = 0; j < sz(v); j++){
		sp[i][j] = sp[i-1][j];
		int k = j + (1<<(i-1));		
		if(k < sz(v) && v[sp[i-1][j]].S > v[sp[i-1][k]].S)
		    sp[i][j] = sp[i-1][k];
	    }
	}
    }
};

int LST[maxn];
vector<pii> conf, p, tell[maxn];
pii ans[maxn];

vector<int> tdo[4 * maxn];

void place(int f, int s, int x, int l = 0, int r = sz(conf) + 1, int id = 1){
    if(f >= s || s <= l || r <= f)
	return;
    if(f <= l && r <= s){
	tdo[id].PB(x);
	return;
    }
    int mid = (l+r) >> 1;
    place(f, s, x, l, mid, 2*id);
    place(f, s, x, mid, r, 2*id+1);    
}

bigTraingle tr;

void solve(int l = 0, int r = sz(conf) + 1, int id = 1){
    if(r-l == 1){
	for(pii x : tell[l]){
	    ans[x.S] = p[x.F];
	}
    }
    if(r-l > 1){
	int mid = (l+r) >> 1;
	solve(l, mid, 2*id);
	solve(mid, r, 2*id + 1);
    }
    if(r == sz(conf) + 1)
	assert(tdo[id].empty());
    if(tdo[id].empty())
	return;
    tr.restart();
    for(int i = l; i < r; i++)
	tr.add(conf[i].F, conf[i].S);
    tr.prepare();
    for(int i : tdo[id])
	p[i] = tr.calc(p[i]);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();
 
    int m, q;
    cin >> N >> m >> q;    
    p.resize(m);
    for(int i = 0; i < m; i++){
	cin >> p[i].F >> p[i].S;
    }
    int Q = 0;
    for(int i = 0; i < q; i++){
	int task;
	cin >> task;
	if(task == 1){
	    int id;
	    cin >> id;
	    --id;
	    //	    tell[sz(conf)].PB({id, Q++});
	    //	    place(LST[id], sz(conf), id);


	    tr.restart();
	    for(int w = LST[id]; w < sz(conf); w++)
		tr.add(conf[w].F, conf[w].S);
	    tr.prepare();
	    p[id] = tr.calc(p[id]);
	    ans[Q++] = p[id];

	    
	    LST[id] = sz(conf);
	}
	if(task == 2){
	    int l;
	    cin >> l;
	    conf.PB({l, 1});
	}
	if(task == 3){
	    int l;
	    cin >> l;
	    conf.PB({l, 0});
	}
	if(task == 4){
	    int x, y;
	    cin >> x >> y;
	    LST[sz(p)] = sz(conf);
	    p.PB({x, y});
	}	
    }
    //    solve();
    for(int i = 0; i < Q; i++){
	cout << ans[i].F << " " << ans[i].S << "\n";
    }
    return 0;
}

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 616 ms 235800 KB Output is correct
2 Correct 369 ms 235640 KB Output is correct
3 Correct 159 ms 235384 KB Output is correct
4 Correct 632 ms 235640 KB Output is correct
5 Correct 146 ms 235512 KB Output is correct
6 Correct 311 ms 235384 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 11.0

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

Subtask #4
0 / 53.0

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

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 616 ms 235800 KB Output is correct
2 Correct 369 ms 235640 KB Output is correct
3 Correct 159 ms 235384 KB Output is correct
4 Correct 632 ms 235640 KB Output is correct
5 Correct 146 ms 235512 KB Output is correct
6 Correct 311 ms 235384 KB Output is correct
7 Execution timed out 18091 ms 243064 KB Time limit exceeded
8 Halted 0 ms 0 KB -