Submission #331296

#	Time	Username	Problem	Language	Result	Execution time	Memory
331296		limabeans	Sweeping (JOI20_sweeping)	C++17	10 / 100	4811 ms	274964 KiB

sweeping

#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
• Subtask 2: 10 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25