oj.uz

Submission #1047010

# Submission time Handle Problem Language Result Execution time Memory
1047010 2024-08-07T07:37:15 Z 우민규(#11023) Sweeping (JOI20_sweeping) C++17
10 / 100
 690 ms 86956 KB 
#include <bits/stdc++.h>
using namespace std;

// range max segment tree
struct Seg {
    int n;
    vector<int> seg;

    Seg(int n, int init) : n(n), seg(4 * n, init) {};

    void add(int node, int l, int r, int idx, int value) {
        if (idx < l || idx >= r) return;
        if (l + 1 == r) {
            seg[node] = max(seg[node], value);
            return;
        }
        int m = (l + r) / 2;
        add(2 * node + 1, l, m, idx, value);
        add(2 * node + 2, m, r, idx, value);

        seg[node] = max(seg[2 * node + 1], seg[2 * node + 2]);
    }
    void add(int idx, int value) { add(0, 0, n, idx, value); }

    // first j >= i s.t. arr[j] >= value
    int find_first_ge(int node, int l, int r, int idx, int value) {
        if (r <= idx || seg[node] < value) return r;
        if (l + 1 == r) return seg[node] >= value ? l : r;

        int m = (l + r) / 2;

        int left = find_first_ge(2 * node + 1, l, m, idx, value);
        if (left == m) return find_first_ge(2 * node + 2, m, r, idx, value);
        return left;
    }
    int find_first_ge(int idx, int value) {
        return find_first_ge(0, 0, n, idx, value);
    }
};

vector<pair<int, int>> pts;

int n, m, q;
vector<int> pts_time;
vector<pair<int, int>> queries;

vector<int> xs, ys;

void solve() {
    cin >> n >> m >> q;
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        pts.push_back({x, y}), pts_time.push_back(-1);
        xs.push_back(x), ys.push_back(y);
    }
    for (int i = 0; i < q; ++i) {
        int t;
        cin >> t;
        if (t == 1) {
            int p;
            cin >> p;
            queries.push_back({t, p - 1});
        }
        if (t == 2 || t == 3) {
            int l;
            cin >> l;
            queries.push_back({t, l});
            if (t == 2) ys.push_back(l);
            else xs.push_back(l);
        }
        if (t == 4) {
            int x, y;
            cin >> x >> y;
            pts.push_back({x, y}), pts_time.push_back(i);
            xs.push_back(x), ys.push_back(y);
            queries.push_back({t, pts.size() - 1});
        }
    }
    sort(xs.begin(), xs.end()), sort(ys.begin(), ys.end());
    xs.resize(unique(xs.begin(), xs.end()) - xs.begin()),
        ys.resize(unique(ys.begin(), ys.end()) - ys.begin());

    Seg x_query(xs.size(), INT_MIN), y_query(ys.size(), INT_MIN);

    auto compx = [&](int xx) { return lower_bound(xs.begin(), xs.end(), xx) - xs.begin(); };
    auto compy = [&](int yy) { return lower_bound(ys.begin(), ys.end(), yy) - ys.begin(); };

    int time = 0;
    for (auto [t, i] : queries) {
        if (t == 1) {
            auto [x, y] = pts[i];
            int ptime = pts_time[i];
            // do x_query first
            int idxx = x_query.find_first_ge(compx(x), ptime);
            int locx = idxx == xs.size() ? n : xs[idxx];
            y = max(y, n - locx);

            int idxy = y_query.find_first_ge(compy(y), ptime);
            int locy = idxy == ys.size() ? n : ys[idxy];
            x = max(x, n - locy);

            cout << x << " " << y << "\n";
        }
        if (t == 2) {
            y_query.add(compy(i), time);
        }
        if (t == 3) {
            x_query.add(compx(i), time);
        }
        if (t == 4) {
            // nothing to do
        }
        time += 1;
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    solve();
}

Compilation message

sweeping.cpp: In function 'void solve()':
sweeping.cpp:96:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |             int locx = idxx == xs.size() ? n : xs[idxx];
      |                        ~~~~~^~~~~~~~~~~~
sweeping.cpp:100:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             int locy = idxy == ys.size() ? n : ys[idxy];
      |                        ~~~~~^~~~~~~~~~~~
sweeping.cpp: In function 'int main()':
sweeping.cpp:120:9: warning: unused variable 't' [-Wunused-variable]
  120 |     int t = 1;
      |         ^

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Incorrect 2 ms 600 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 658 ms 66800 KB Output is correct
2 Correct 648 ms 79532 KB Output is correct
3 Correct 684 ms 79136 KB Output is correct
4 Correct 541 ms 76460 KB Output is correct
5 Correct 525 ms 82352 KB Output is correct
6 Correct 621 ms 86956 KB Output is correct
7 Correct 630 ms 85644 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 690 ms 60352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 690 ms 60352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Incorrect 2 ms 600 KB Output isn't correct
3 Halted 0 ms 0 KB -