oj.uz

Submission #331296

# Submission time Handle Problem Language Result Execution time Memory
331296 2020-11-28T01:22:18 Z limabeans Sweeping (JOI20_sweeping) C++17
10 / 100
 4811 ms 274964 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;



int n,m,q;
pair<int,int> P[maxn];

int inp[maxn];


set<int> s[maxn];

void insert(int t, int val) {
    for (; t<=q; t+=t&-t) {
	s[t].insert(val);
    }
}

int qry(int t, int val) {
    int res = 0;
    
    for (; t>0; t-=t&-t) {
	auto iter = s[t].lower_bound(val);
	res = max(res, iter==s[t].end() ? 0 : n - *iter);
    }
    return res;
}

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

    cin>>n>>m>>q;

    for (int i=1; i<=m; i++) {
	cin>>P[i].first>>P[i].second;
	inp[i] = q+1;
    }


    set<int> horiz;


    for (int z=1; z<=q; z++) {
        int op;
	cin>>op;
	if (op==4) {
	    // add dust
	    int x,y; cin>>x>>y;
	    ++m;
	    P[m] = {x,y};
	    inp[m] = q-z+1;
	} else if (op==3) {
	    assert(false);
	    // vertical
	} else if (op==2) {
	    // horizontal
	    int l;
	    cin>>l;
	    insert(q-z+1,l);
	} else if (op==1) {
	    int i;
	    cin>>i;
	    P[i].first = max(P[i].first, qry(inp[i], P[i].second));
	    cout<<P[i].first<<" "<<P[i].second<<"\n";
	}
    }
    return 0;
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Runtime error 93 ms 95852 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4540 ms 267664 KB Output is correct
2 Correct 4571 ms 274956 KB Output is correct
3 Correct 4306 ms 274964 KB Output is correct
4 Correct 2460 ms 273800 KB Output is correct
5 Correct 2458 ms 274692 KB Output is correct
6 Correct 3821 ms 269252 KB Output is correct
7 Correct 4811 ms 274756 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 210 ms 110444 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Runtime error 210 ms 110444 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 93 ms 95852 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -