oj.uz

Submission #257729

# Submission time Handle Problem Language Result Execution time Memory
257729 2020-08-04T16:08:00 Z Bruteforceman Sweeping (JOI20_sweeping) C++11
100 / 100
 16197 ms 326468 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxm = 1.5e6 + 10;
int X[maxm], Y[maxm];
pair <int, int> ans[maxm];
int n;

struct info {
  int t, p;
  int idx;
  info () {}
};
info index(int i) {
  info x;
  x.t = 4;
  x.idx = i;
  return x;
}
struct ds {
  int par[maxm], value[maxm];
  vector <int> cont[maxm];
  priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> Q;
  void init() {
    while(!Q.empty()) Q.pop();
  }
  int root(int x) {
    if(par[x] == x) return x;
    return par[x] = root(par[x]);
  }
  void joinIdx(int x, int y) {
    x = root(x);
    y = root(y);
    if(x != y) {
      if(cont[x].size() > cont[y].size()) swap(x, y);
      par[x] = y;
      for(auto i : cont[x]) {
        cont[y].push_back(i);
      }
    }
  }
  void add(int pos, int idx) {
    Q.emplace(pos, idx);
    par[idx] = idx;
    value[idx] = pos;
    cont[idx] = vector <int> ({idx}) ;
  }
  int getPos(int idx) {
    return value[root(idx)];
  }
  vector <int> getIndex(int pos) {
    vector <int> ans; 
    while(!Q.empty()) {
      int x = Q.top().first;
      int idx = Q.top().second;
      if(x <= pos) {
        Q.pop();
        for(int i : cont[idx]) {
          ans.push_back(i);
        }
      } else break;
    }
    return ans;
  }
  void move(int pos) {
    int last = -1;
    while(!Q.empty()) {
      int x = Q.top().first;
      int idx = Q.top().second;
      if(x <= pos) {
        Q.pop();
        if(last != -1) joinIdx(last, idx);
        last = idx;
      } else break;
    }
    if(last != -1) {
      value[root(last)] = pos;
      Q.emplace(pos, root(last));
    }
  }
} contX, contY; 

void solve(int xa, int ya, vector <info> &v) {
  if(v.empty()) return ;
  int midX = (xa + n - ya) / 2;
  int midY = n - midX;

  vector <info> left, right;
  map <int, int> side;
  contX.init();
  contY.init();
  for(auto i : v) {
    if(i.t == 1) {
      if(side.find(i.p) == side.end()) {
        ans[i.idx] = make_pair(contX.getPos(i.p), contY.getPos(i.p));
      } else {
        if(side[i.p]) right.push_back(i);
        else left.push_back(i);
      }
    } else if (i.t == 2) {
      if(i.p < midY) {
        auto u = contY.getIndex(i.p);
        for(auto j : u) {
          if(side.find(j) != side.end()) continue;
          X[j] = n - i.p;
          Y[j] = contY.getPos(j);
          right.push_back(index(j));
          side[j] = 1;
        }
        right.push_back(i);
      } else {
        contX.move(n - i.p);
        left.push_back(i);
      }
    } else if (i.t == 3) {
      if(i.p < midX) {
        auto u = contX.getIndex(i.p);
        for(auto j : u) {
          if(side.find(j) != side.end()) continue;
          X[j] = contX.getPos(j);
          Y[j] = n - i.p;
          left.push_back(index(j));
          side[j] = 0;
        }
        left.push_back(i);
      } else {
        contY.move(n - i.p);
        right.push_back(i);
      }
    } else {
      if(X[i.idx] <= midX && Y[i.idx] <= midY) {
        contX.add(X[i.idx], i.idx);
        contY.add(Y[i.idx], i.idx);
      } else if (midX < X[i.idx]) {
        side[i.idx] = 1;
        right.push_back(i);
      } else {
        side[i.idx] = 0;
        left.push_back(i);
      }
    }
  }
  v.clear();
  side.clear();
  if(ya <= midY + 1 && midY + 1 <= n - xa) {
    solve(xa, midY + 1, left);
  }
  if(xa <= midX + 1 && midX + 1 <= n - ya) {
    solve(midX + 1, ya, right);
  }
}

int main() {
  int m, q;
  scanf("%d %d %d", &n, &m, &q);
  vector <info> v;
  for(int i = 1; i <= m; i++) {
    info add;
    add.t = 4;
    add.idx = i;
    scanf("%d %d", &X[i], &Y[i]);
    v.push_back(add);
  }
  for(int i = 1; i <= q; i++) {
    info add;
    scanf("%d", &add.t);
    if(add.t == 1) {
      scanf("%d", &add.p);
      add.idx = i;
    }
    else if (add.t == 2) scanf("%d", &add.p);
    else if (add.t == 3) scanf("%d", &add.p);
    else {
      add.idx = ++m;
      scanf("%d %d", &X[m], &Y[m]);
    }
    v.push_back(add);
  }
  auto u = v;
  solve(0, 0, u);
  for(auto i : v) {
    if(i.t == 1) printf("%d %d\n", ans[i.idx].first, ans[i.idx].second);
  }
  return 0;
}

Compilation message

sweeping.cpp: In function 'int main()':
sweeping.cpp:154:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &n, &m, &q);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:160:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &X[i], &Y[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:165:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &add.t);
     ~~~~~^~~~~~~~~~~~~~
sweeping.cpp:167:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &add.p);
       ~~~~~^~~~~~~~~~~~~~
sweeping.cpp:170:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     else if (add.t == 2) scanf("%d", &add.p);
                          ~~~~~^~~~~~~~~~~~~~
sweeping.cpp:171:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     else if (add.t == 3) scanf("%d", &add.p);
                          ~~~~~^~~~~~~~~~~~~~
sweeping.cpp:174:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &X[m], &Y[m]);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 71672 KB Output is correct
2 Correct 54 ms 71296 KB Output is correct
3 Correct 48 ms 71552 KB Output is correct
4 Correct 60 ms 71772 KB Output is correct
5 Correct 58 ms 71800 KB Output is correct
6 Correct 49 ms 71544 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8309 ms 207600 KB Output is correct
2 Correct 8170 ms 207464 KB Output is correct
3 Correct 8256 ms 217372 KB Output is correct
4 Correct 9831 ms 251048 KB Output is correct
5 Correct 12885 ms 227808 KB Output is correct
6 Correct 12829 ms 252712 KB Output is correct
7 Correct 8029 ms 238564 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6193 ms 207112 KB Output is correct
2 Correct 6783 ms 211208 KB Output is correct
3 Correct 5487 ms 231888 KB Output is correct
4 Correct 5844 ms 253576 KB Output is correct
5 Correct 7227 ms 258804 KB Output is correct
6 Correct 6380 ms 232364 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 6193 ms 207112 KB Output is correct
2 Correct 6783 ms 211208 KB Output is correct
3 Correct 5487 ms 231888 KB Output is correct
4 Correct 5844 ms 253576 KB Output is correct
5 Correct 7227 ms 258804 KB Output is correct
6 Correct 6380 ms 232364 KB Output is correct
7 Correct 7769 ms 223712 KB Output is correct
8 Correct 7840 ms 221864 KB Output is correct
9 Correct 7734 ms 222892 KB Output is correct
10 Correct 9909 ms 244080 KB Output is correct
11 Correct 11396 ms 271932 KB Output is correct
12 Correct 14529 ms 253664 KB Output is correct
13 Correct 13723 ms 305760 KB Output is correct
14 Correct 302 ms 128432 KB Output is correct
15 Correct 2734 ms 204972 KB Output is correct
16 Correct 7436 ms 222764 KB Output is correct
17 Correct 7660 ms 222104 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 71672 KB Output is correct
2 Correct 54 ms 71296 KB Output is correct
3 Correct 48 ms 71552 KB Output is correct
4 Correct 60 ms 71772 KB Output is correct
5 Correct 58 ms 71800 KB Output is correct
6 Correct 49 ms 71544 KB Output is correct
7 Correct 8309 ms 207600 KB Output is correct
8 Correct 8170 ms 207464 KB Output is correct
9 Correct 8256 ms 217372 KB Output is correct
10 Correct 9831 ms 251048 KB Output is correct
11 Correct 12885 ms 227808 KB Output is correct
12 Correct 12829 ms 252712 KB Output is correct
13 Correct 8029 ms 238564 KB Output is correct
14 Correct 6193 ms 207112 KB Output is correct
15 Correct 6783 ms 211208 KB Output is correct
16 Correct 5487 ms 231888 KB Output is correct
17 Correct 5844 ms 253576 KB Output is correct
18 Correct 7227 ms 258804 KB Output is correct
19 Correct 6380 ms 232364 KB Output is correct
20 Correct 7769 ms 223712 KB Output is correct
21 Correct 7840 ms 221864 KB Output is correct
22 Correct 7734 ms 222892 KB Output is correct
23 Correct 9909 ms 244080 KB Output is correct
24 Correct 11396 ms 271932 KB Output is correct
25 Correct 14529 ms 253664 KB Output is correct
26 Correct 13723 ms 305760 KB Output is correct
27 Correct 302 ms 128432 KB Output is correct
28 Correct 2734 ms 204972 KB Output is correct
29 Correct 7436 ms 222764 KB Output is correct
30 Correct 7660 ms 222104 KB Output is correct
31 Correct 8619 ms 243260 KB Output is correct
32 Correct 8525 ms 228776 KB Output is correct
33 Correct 6640 ms 234028 KB Output is correct
34 Correct 8989 ms 261292 KB Output is correct
35 Correct 8807 ms 261176 KB Output is correct
36 Correct 11338 ms 253988 KB Output is correct
37 Correct 14080 ms 312492 KB Output is correct
38 Correct 16197 ms 326468 KB Output is correct
39 Correct 13268 ms 300988 KB Output is correct
40 Correct 8406 ms 248188 KB Output is correct