oj.uz

Submission #259781

# Submission time Handle Problem Language Result Execution time Memory
259781 2020-08-08T14:12:38 Z shayan_p Sweeping (JOI20_sweeping) C++14
64 / 100
 12115 ms 1527368 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{
    map<int, int> mp;
    void add(int f, int s, int x){
	auto L = mp.upper_bound(f);
	int col = -1;
	if(L != mp.begin())
	    col = prev(L)->S;
	auto R = L;
	while(R != mp.end() && (R->F) <= s)
	    col = R->S, R++;
	mp[f] = x;
	mp[s] = col;
    }
    int ask(int pos){
	auto it = mp.upper_bound(pos);
	if(it == mp.begin())
	    return -1;
	return prev(it)->S;
    }
};

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;
	}
    }
};
    
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

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Runtime error 174 ms 8440 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

# Verdict Execution time Memory Grader output
1 Correct 10399 ms 1296252 KB Output is correct
2 Correct 7307 ms 1349360 KB Output is correct
3 Correct 11473 ms 1527368 KB Output is correct
4 Correct 8176 ms 1313876 KB Output is correct
5 Correct 7156 ms 1319152 KB Output is correct
6 Correct 7763 ms 1275288 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 10399 ms 1296252 KB Output is correct
2 Correct 7307 ms 1349360 KB Output is correct
3 Correct 11473 ms 1527368 KB Output is correct
4 Correct 8176 ms 1313876 KB Output is correct
5 Correct 7156 ms 1319152 KB Output is correct
6 Correct 7763 ms 1275288 KB Output is correct
7 Correct 7841 ms 1346068 KB Output is correct
8 Correct 8121 ms 1350592 KB Output is correct
9 Correct 7830 ms 1348220 KB Output is correct
10 Correct 11686 ms 1526780 KB Output is correct
11 Correct 8183 ms 1312928 KB Output is correct
12 Correct 7766 ms 1274452 KB Output is correct
13 Correct 8057 ms 1249584 KB Output is correct
14 Correct 445 ms 12252 KB Output is correct
15 Correct 658 ms 30088 KB Output is correct
16 Correct 12115 ms 1257620 KB Output is correct
17 Correct 8164 ms 1274800 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory 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 -