Submission #1004310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004310		Unforgettablepl	Sweeping (JOI20_sweeping)	C++17	0 / 100	18038 ms	283288 KiB

sweeping

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

#define int long long

typedef tree<pair<int,int>,null_type,less<>,rb_tree_tag,tree_order_statistics_node_update> orderedset;

struct triangle{
    mutable orderedset x,y;
    triangle(){}
    bool operator<(const triangle& other) const {return false;}
};

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,q;
    cin >> n >> m >> q;
    vector<int const*> pos(m+1);
    vector<pair<int,int>> defaultpos(m+1);
    set<pair<int,triangle>> room;
    set<int> points = {0,n};
    room.insert({n,{}});
    for(int i=1;i<=m;i++){
        int x,y;cin>>x>>y;
        defaultpos[i]={x,y};
        room.begin()->second.x.insert({x,i});
        room.begin()->second.y.insert({y,i});
        pos[i] = &(room.begin()->first);
    }
    for(int i=1;i<=q;i++){
        int type;cin>>type;
        if(type==1){
            int x;cin>>x;
            // CALCULATE POSITION OF DUST x
            int curr = 0,before=0;
            if(pos[x]!=nullptr){
                curr = *pos[x];
                before = *--points.lower_bound(curr);
                curr = n-curr;
            }
            cout << max(defaultpos[x].first,curr) << ' ' << max(defaultpos[x].second,before) << '\n';
        } else if(type==2){
            int l;cin>>l;
            auto curr = room.extract(room.lower_bound({l,{}}));
            if(l==curr.value().first){
                room.insert(move(curr));
                curr = room.extract(room.upper_bound({l,{}}));
                while(curr.value().second.y.size() and (*curr.value().second.y.begin()).first<=l){
                    auto idx = (*curr.value().second.y.begin()).second;
                    defaultpos[idx] = {n-l,l};
                    pos[idx] = nullptr;
                    curr.value().second.x.erase(curr.value().second.x.find(make_pair(defaultpos[idx].first,idx)));
                    curr.value().second.y.erase(curr.value().second.y.find(make_pair(defaultpos[idx].second,idx)));
                }
                room.insert(move(curr));
                continue;
            }
            if(2*curr.value().second.y.order_of_key({l,0})>curr.value().second.y.size()){
                // Modify current one
                auto newer = triangle();
                vector<int> buffer;
                while(curr.value().second.y.size() and (*--curr.value().second.y.end()).first>l){
                    auto idx = (*--curr.value().second.y.end()).second;
                    newer.x.insert(make_pair(defaultpos[idx].first,idx));
                    newer.y.insert(make_pair(defaultpos[idx].second,idx));
                    curr.value().second.x.erase(curr.value().second.x.find(make_pair(defaultpos[idx].first,idx)));
                    curr.value().second.y.erase(curr.value().second.y.find(make_pair(defaultpos[idx].second,idx)));
                    buffer.emplace_back(idx);
                }
                auto ptr = &(room.insert({curr.value().first,newer}).first->first);
                for(int&x:buffer)pos[x]=ptr;
                curr.value().first = l;
                room.insert(move(curr));
            } else {
                // Modify new one
                auto newer = triangle();
                vector<int> buffer;
                while(curr.value().second.y.size() and (*curr.value().second.y.begin()).first<=l){
                    auto idx = (*curr.value().second.y.begin()).second;
                    newer.x.insert(make_pair(defaultpos[idx].first,idx));
                    newer.y.insert(make_pair(defaultpos[idx].second,idx));
                    curr.value().second.x.erase(curr.value().second.x.find(make_pair(defaultpos[idx].first,idx)));
                    curr.value().second.y.erase(curr.value().second.y.find(make_pair(defaultpos[idx].second,idx)));
                    buffer.emplace_back(idx);
                }
                auto ptr = &(room.insert({l,newer}).first->first);
                for(int&x:buffer)pos[x]=ptr;
                room.insert(move(curr));
            }
            points.insert(l);
        } else if(type==3){
            int l;cin>>l;int lx = n-l;
            auto curr = room.extract(room.lower_bound({lx,{}}));
            if(lx==curr.value().first){
                while(curr.value().second.x.size() and (*curr.value().second.x.begin()).first<=l){
                    auto idx = (*curr.value().second.x.begin()).second;
                    defaultpos[idx]={l,lx};
                    pos[idx]=nullptr;
                    curr.value().second.x.erase(curr.value().second.x.find(make_pair(defaultpos[idx].first,idx)));
                    curr.value().second.y.erase(curr.value().second.y.find(make_pair(defaultpos[idx].second,idx)));
                }
                room.insert(move(curr));
                continue;
            }
            if(2*curr.value().second.x.order_of_key({l,0})>curr.value().second.x.size()){
                // Modify newer one
                auto newer = triangle();
                vector<int> buffer;
                while(curr.value().second.x.size() and (*--curr.value().second.x.end()).first>l){
                    auto idx = (*--curr.value().second.x.end()).second;
                    newer.x.insert(make_pair(defaultpos[idx].first,idx));
                    newer.y.insert(make_pair(defaultpos[idx].second,idx));
                    curr.value().second.x.erase(curr.value().second.x.find(make_pair(defaultpos[idx].first,idx)));
                    curr.value().second.y.erase(curr.value().second.y.find(make_pair(defaultpos[idx].second,idx)));
                    buffer.emplace_back(idx);
                }
                auto ptr = &(room.insert({lx,newer}).first->first);
                for(int&x:buffer)pos[x]=ptr;
                room.insert(move(curr));
            } else {
                // Modify current one
                auto newer = triangle();
                vector<int> buffer;
                while(curr.value().second.x.size() and (*curr.value().second.x.begin()).first<=l){
                    auto idx = (*curr.value().second.x.begin()).second;
                    newer.x.insert(make_pair(defaultpos[idx].first,idx));
                    newer.y.insert(make_pair(defaultpos[idx].second,idx));
                    curr.value().second.x.erase(curr.value().second.x.find(make_pair(defaultpos[idx].first,idx)));
                    curr.value().second.y.erase(curr.value().second.y.find(make_pair(defaultpos[idx].second,idx)));
                    buffer.emplace_back(idx);
                }
                auto ptr = &(room.insert({curr.value().first,newer}).first->first);
                for(int&x:buffer)pos[x]=ptr;
                curr.value().first = lx;
                room.insert(move(curr));
            }
            points.insert(lx);
        }
    }
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25