Submission #218678

#	Time	Username	Problem	Language	Result	Execution time	Memory
218678		eriksuenderhauf	Sweeping (JOI20_sweeping)	C++11	100 / 100	8414 ms	350064 KiB

sweeping

//#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 (stderr)

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