Submission #1049187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049187		kostia244	Sweeping (JOI20_sweeping)	C++17	100 / 100	10564 ms	779428 KiB

sweeping

#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;

struct Query {
    int type, v, x, y;
};

struct RectSweep {
    map<int, vector<int>> CtoP[2];
    vector<array<int, 2>> pts;
    vector<int> real_id;
    map<int, int> local_id;
    vector<int> pt_color[2];
    vector<int> col_coord[2];
    void addPoint(array<int, 2> P, int id) {
        for(int i = 0; i < 2; i++) {
            CtoP[i][P[i]].push_back(pts.size());
            
            if(CtoP[i][P[i]].size() == 1) {
                pt_color[i].push_back(col_coord[i].size());
                col_coord[i].push_back(P[i]);
            } else {
                pt_color[i].push_back(pt_color[i][CtoP[i][P[i]][0]]);
            }
        }
        
        real_id.push_back(id);
        local_id[id] = pts.size();
        pts.push_back(P);
    }
    
    void combine(vector<int> &a, vector<int> &b, int dir) {
        if(a.size() < b.size()) swap(a, b);
        for(auto &i : b) {
            a.push_back(i);
            pt_color[dir][i] = pt_color[dir][a[0]];
        }
    }
    
    void sweep(int dir, int lim) {//coord_dir max=
        while(CtoP[dir].size() && CtoP[dir].begin()->first < lim) {
            combine(CtoP[dir][lim], CtoP[dir].begin()->second, dir);
            CtoP[dir].erase(CtoP[dir].begin());
            
            int col = pt_color[dir][CtoP[dir][lim][0]];
            col_coord[dir][col] = lim;
        }
    }
    
    vector<array<int, 3>> extract(int dir, int lim) {//delete coord_dir <= lim
        vector<array<int, 3>> res;
        while(CtoP[dir].size() && CtoP[dir].begin()->first <= lim) {
            for(auto i : CtoP[dir].begin()->second) {
                if(real_id[i] != -1) {
                    int X = col_coord[0][pt_color[0][i]];
                    int Y = col_coord[1][pt_color[1][i]];
                    res.push_back({real_id[i], X, Y});
                    real_id[i] = -1 - dir;
                }
            }
            
            CtoP[dir].erase(CtoP[dir].begin());
        }
        
        return res;
    }
    
    array<int, 2> getPoint(int rid) {
        if(!local_id.count(rid)) return {-1, -1};//never inserted
        int lid = local_id[rid];
        if(real_id[lid] < 0) return {-1, -1};//point already extracted
        return {col_coord[0][pt_color[0][lid]], 
            col_coord[1][pt_color[1][lid]]};
    }
};

void test_rs() {
    
    RectSweep rs;
    rs.addPoint({3, 3}, 100);
    rs.addPoint({0, 0}, 1);
    rs.sweep(0, 10);
    for(auto [i, x, y] : rs.extract(1, 0)) cout << i << " " << x << " " << y << "; "; cout << endl;
    rs.addPoint({0, 0}, 10);
    rs.sweep(1, 12);
    rs.sweep(0, 3);
    for(auto [i, x, y] : rs.extract(0, 9)) cout << i << " " << x << " " << y << "; "; cout << endl;
    for(auto [i, x, y] : rs.extract(0, 10)) cout << i << " " << x << " " << y << "; "; cout << endl;
    
    
    
    exit(0);
}

void solve(int n, vector<Query> queries, vector<array<int, 2>> &ans, int start_x, int start_y) {
    if(queries.empty()) return;
    // cout << "_____"<<endl;
    // cout << n << " " << queries.size() << " cc " << start_x << " " << start_y << endl;
    // for(auto &q : queries) {
    //     cout << q.type << " " << q.v << " " << q.x << " " << q.y << endl;
    // }
    
    int r = n / 2; 
    array<vector<Query>, 2> push;//0 for top, 1 for right
    map<int, int> point_dir;
    RectSweep rc;
    
    for(auto q : queries) {
        if(q.type == 1) {
            auto [x, y] = rc.getPoint(q.v);
            if(x >= 0) {
                ans[q.x] = {start_x + x, start_y + y};
                // cout << q.x << " :: " << q.v << " " << start_x << " " << start_y << " " << x << " " << y << endl;
            } else {
                assert(point_dir.count(q.v));
                push[point_dir[q.v]].push_back(q);
            }
            
        }
        if(q.type == 2 || q.type == 3) {
            int dir = 3 - q.type;
            int len = q.v;
            // For all P[dir]<=len, P[dir ^ 1] = n - len
            if(n - len > r) {//go up/right
                for(auto [id, x, y] : rc.extract(dir, len)) {
                    point_dir[id] = dir;
                    (dir ? x : y) = n - len;
                    push[dir].push_back(Query{4, id, x, y});
                }
                push[dir].push_back(q);
            } else {//P[dir ^ 1] max= n-len for all
                rc.sweep(dir ^ 1, n - len);
                q.v -= r + 1;
                if(q.v >= 0)
                    push[dir ^ 1].push_back(q);
            }
        }
        if(q.type == 4) {
            if(q.y > r) {
                point_dir[q.v] = 0;
                push[0].push_back(q);
            } else if(q.x > r) {
                point_dir[q.v] = 1;
                push[1].push_back(q);
            } else {
                // cout << "Add " << q.x << " " << q.y << " " << q.v << endl;
                rc.addPoint({q.x, q.y}, q.v);
                // cout << rc.getPoint(q.v)[1] << endl;
                
            }
        }
    }
    
    for(int c = 0; c < 2; c++) {
        for(auto &q : push[c]) {
            if(q.type == 4) {
                (c ? q.x : q.y) -= r+1;
            }
        }
    }

    solve(n - r - 1, push[0], ans, start_x, start_y + r + 1);
    solve(n - r - 1, push[1], ans, start_x + r + 1, start_y);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    // test_rs();
    int n, m, q;
    int num_points = 0, num_ask = 0;
    cin >> n >> m >> q;
    vector<Query> queries(m + q);
    for(int x, y, i = 0; i < m; i++) {
        cin >> x >> y;
        queries[i] = Query{4, num_points++, x, y};
    }
    for(int i = 0; i < q; i++) {
        cin >> queries[m+i].type;
        if(queries[m+i].type == 4) {
            cin >> queries[m+i].x >> queries[m+i].y;
            queries[m+i].v = num_points++;
        } else {
            cin >> queries[m + i].v;
            queries[m + i].v -= (queries[m+i].type == 1);
            if(queries[m+i].type == 1) {
                queries[m+i].x = num_ask++;
            }
        }
    }
    
    vector<array<int, 2>> answers(num_ask);
    solve(n, queries, answers, 0, 0);
    for(auto [x, y] : answers) {
        cout << x << ' ' << y << '\n';
    }
}

Compilation message (stderr)

sweeping.cpp: In function 'void test_rs()':
sweeping.cpp:85:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   85 |     for(auto [i, x, y] : rs.extract(1, 0)) cout << i << " " << x << " " << y << "; "; cout << endl;
      |     ^~~
sweeping.cpp:85:87: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   85 |     for(auto [i, x, y] : rs.extract(1, 0)) cout << i << " " << x << " " << y << "; "; cout << endl;
      |                                                                                       ^~~~
sweeping.cpp:89:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   89 |     for(auto [i, x, y] : rs.extract(0, 9)) cout << i << " " << x << " " << y << "; "; cout << endl;
      |     ^~~
sweeping.cpp:89:87: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   89 |     for(auto [i, x, y] : rs.extract(0, 9)) cout << i << " " << x << " " << y << "; "; cout << endl;
      |                                                                                       ^~~~
sweeping.cpp:90:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   90 |     for(auto [i, x, y] : rs.extract(0, 10)) cout << i << " " << x << " " << y << "; "; cout << endl;
      |     ^~~
sweeping.cpp:90:88: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   90 |     for(auto [i, x, y] : rs.extract(0, 10)) cout << i << " " << x << " " << y << "; "; cout << endl;
      |                                                                                        ^~~~

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