oj.uz

Submission #218678

# Submission time Handle Problem Language Result Execution time Memory
218678 2020-04-02T13:52:37 Z eriksuenderhauf Sweeping (JOI20_sweeping) C++11
100 / 100
 8414 ms 350064 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define trav(x,a) for (const auto& x: a)
#define sz(x) (int)(x).size()
#define pii pair<int, int>
#define vii vector<pii>
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using namespace std;

const int inf = 1e9 + 7;
const int N = 2e6 + 5;
pii a[N], b[N];
int idx[N], n;
pii ans[N], qry[N];
vector<pii> seg[4*N];

void upd(int l, int r, int k, int x, int y, int i, int j) {
  if (r < x || y < l) return;
  if (x <= l && r <= y) {
    seg[k].push_back({i, j});
    return;
  }
  int m = (l+r) / 2;
  upd(l, m, k*2, x, y, i, j);
  upd(m+1, r, k*2+1, x, y, i, j);
}

void solve(int l, int r, int k) {
  if (l < r) {
    int m = (l+r) / 2;
    solve(l, m, k*2);
    solve(m+1, r, k*2+1);
  }
  if (seg[k].empty())
    return;
  sort(seg[k].begin(), seg[k].end(), [](pii lhs, pii rhs) {
    return b[lhs.nd] < b[rhs.nd];
  });
  map<pii,pii> q;
  q[{n, n}] = {0, 0};
  for (int i = l; i <= r; i++) {
    int L = qry[i].nd;
    if (qry[i].st == 2) { // H
      auto it = q.lower_bound({n - L, L});
      if (it->st.nd == L)
        continue;
      pii x = it->st, y = it->nd;
      q.erase(it);
      q[{x.st, L}] = y;
      q[{n - L - 1, x.nd}] = {y.st, L + 1};
    } else { // V
      auto it = q.lower_bound({L, n - L});
      if (it->st.st == L)
        continue;
      pii x = it->st, y = it->nd;
      q.erase(it);
      q[{L, x.nd}] = y;
      q[{x.st, n - L - 1}] = {L + 1, y.nd};
    }
  }
  vector<pair<pii,pii>> arr;
  trav(x, q) arr.push_back(x);
  sort(arr.begin(), arr.end(), [](pair<pii,pii> lhs, pair<pii,pii> rhs) {
    return lhs.nd < rhs.nd;
  });
  int i = 0;
  map<int,pii> act;
  trav(x, seg[k]) {
    while (i < sz(arr) && arr[i].nd.st <= b[x.nd].st) {
      act[arr[i].nd.nd] = arr[i].st;
      i++;
    }
    auto it = prev(act.upper_bound(b[x.nd].nd));
    b[x.nd].st = max(b[x.nd].st, n - it->nd.nd);
    b[x.nd].nd = max(b[x.nd].nd, n - it->nd.st);
    ans[x.st] = b[x.nd];
  }
}

int main() {
  int m, q; scanf("%d %d %d", &n, &m, &q);
  for (int i = 1; i <= m; i++) {
    scanf("%d %d", &a[i].st, &a[i].nd);
    b[i] = a[i];
    idx[i] = 1;
  }
  vector<array<int,4>> ar;
  int j = 0;
  for (int i = 1; i <= q; i++) {
    ans[i] = mp(-1, -1);
    int t, x, y;
    scanf("%d %d", &t, &x);
    if (t == 1) {
      ar.push_back({idx[x], j, i, x});
      idx[x] = j+1;
    } else if (t <= 3) {
      qry[++j] = mp(t, x);
    } else if (t == 4) {
      scanf("%d", &y);
      a[++m] = mp(x, y);
      b[m] = a[m];
      idx[m] = j+1;
    }
  }
  trav(x, ar)
    if (x[0] <= x[1] && j)
      upd(1, j, 1, x[0], x[1], x[2], x[3]);
  solve(1, j, 1);
  trav(x, ar) {
    if (ans[x[2]] != mp(-1, -1))
      a[x[3]] = ans[x[2]];
    printf("%d %d\n", a[x[3]].st, a[x[3]].nd);
  }
  return 0;
}

Compilation message

sweeping.cpp: In function 'int main()':
sweeping.cpp:84:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int m, q; scanf("%d %d %d", &n, &m, &q);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &a[i].st, &a[i].nd);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &t, &x);
     ~~~~~^~~~~~~~~~~~~~~~~
sweeping.cpp:102:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &y);
       ~~~~~^~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 188792 KB Output is correct
2 Correct 127 ms 188664 KB Output is correct
3 Correct 111 ms 188408 KB Output is correct
4 Correct 121 ms 188804 KB Output is correct
5 Correct 113 ms 188444 KB Output is correct
6 Correct 112 ms 188664 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6240 ms 337236 KB Output is correct
2 Correct 5326 ms 313984 KB Output is correct
3 Correct 5265 ms 313760 KB Output is correct
4 Correct 4641 ms 314356 KB Output is correct
5 Correct 4604 ms 345568 KB Output is correct
6 Correct 1895 ms 291236 KB Output is correct
7 Correct 5655 ms 314128 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7168 ms 338384 KB Output is correct
2 Correct 6659 ms 340996 KB Output is correct
3 Correct 5827 ms 347780 KB Output is correct
4 Correct 5266 ms 319288 KB Output is correct
5 Correct 6746 ms 335436 KB Output is correct
6 Correct 6916 ms 319376 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 7168 ms 338384 KB Output is correct
2 Correct 6659 ms 340996 KB Output is correct
3 Correct 5827 ms 347780 KB Output is correct
4 Correct 5266 ms 319288 KB Output is correct
5 Correct 6746 ms 335436 KB Output is correct
6 Correct 6916 ms 319376 KB Output is correct
7 Correct 6517 ms 319432 KB Output is correct
8 Correct 6409 ms 319336 KB Output is correct
9 Correct 6214 ms 319432 KB Output is correct
10 Correct 5536 ms 318880 KB Output is correct
11 Correct 5392 ms 319228 KB Output is correct
12 Correct 8414 ms 350064 KB Output is correct
13 Correct 6553 ms 319232 KB Output is correct
14 Correct 344 ms 207736 KB Output is correct
15 Correct 749 ms 247364 KB Output is correct
16 Correct 6892 ms 324420 KB Output is correct
17 Correct 1742 ms 297876 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 188792 KB Output is correct
2 Correct 127 ms 188664 KB Output is correct
3 Correct 111 ms 188408 KB Output is correct
4 Correct 121 ms 188804 KB Output is correct
5 Correct 113 ms 188444 KB Output is correct
6 Correct 112 ms 188664 KB Output is correct
7 Correct 6240 ms 337236 KB Output is correct
8 Correct 5326 ms 313984 KB Output is correct
9 Correct 5265 ms 313760 KB Output is correct
10 Correct 4641 ms 314356 KB Output is correct
11 Correct 4604 ms 345568 KB Output is correct
12 Correct 1895 ms 291236 KB Output is correct
13 Correct 5655 ms 314128 KB Output is correct
14 Correct 7168 ms 338384 KB Output is correct
15 Correct 6659 ms 340996 KB Output is correct
16 Correct 5827 ms 347780 KB Output is correct
17 Correct 5266 ms 319288 KB Output is correct
18 Correct 6746 ms 335436 KB Output is correct
19 Correct 6916 ms 319376 KB Output is correct
20 Correct 6517 ms 319432 KB Output is correct
21 Correct 6409 ms 319336 KB Output is correct
22 Correct 6214 ms 319432 KB Output is correct
23 Correct 5536 ms 318880 KB Output is correct
24 Correct 5392 ms 319228 KB Output is correct
25 Correct 8414 ms 350064 KB Output is correct
26 Correct 6553 ms 319232 KB Output is correct
27 Correct 344 ms 207736 KB Output is correct
28 Correct 749 ms 247364 KB Output is correct
29 Correct 6892 ms 324420 KB Output is correct
30 Correct 1742 ms 297876 KB Output is correct
31 Correct 5050 ms 311548 KB Output is correct
32 Correct 5279 ms 307396 KB Output is correct
33 Correct 5810 ms 312764 KB Output is correct
34 Correct 6226 ms 330568 KB Output is correct
35 Correct 5130 ms 310116 KB Output is correct
36 Correct 4849 ms 319412 KB Output is correct
37 Correct 4681 ms 315244 KB Output is correct
38 Correct 6714 ms 341232 KB Output is correct
39 Correct 6048 ms 320512 KB Output is correct
40 Correct 5946 ms 312516 KB Output is correct