oj.uz

Submission #257727

# Submission time Handle Problem Language Result Execution time Memory
257727 2020-08-04T16:04:52 Z Bruteforceman Sweeping (JOI20_sweeping) C++11
1 / 100
 18000 ms 986784 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 {
  map <int, int> par, value;
  map <int, vector <int>> cont;
  priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> Q;
  ds () {}
  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));
    }
  }
}; 

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;
  ds contX, contY;
  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:151: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:157: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:162:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &add.t);
     ~~~~~^~~~~~~~~~~~~~
sweeping.cpp:164:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &add.p);
       ~~~~~^~~~~~~~~~~~~~
sweeping.cpp:167: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:168: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:171: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 35 ms 2304 KB Output is correct
2 Correct 17 ms 1176 KB Output is correct
3 Correct 16 ms 1904 KB Output is correct
4 Correct 45 ms 2552 KB Output is correct
5 Correct 39 ms 2860 KB Output is correct
6 Correct 11 ms 2432 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14156 ms 142636 KB Output is correct
2 Correct 13354 ms 142452 KB Output is correct
3 Correct 12760 ms 144044 KB Output is correct
4 Correct 13887 ms 304476 KB Output is correct
5 Execution timed out 18122 ms 406224 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14662 ms 290420 KB Output is correct
2 Correct 16470 ms 325136 KB Output is correct
3 Correct 7477 ms 264492 KB Output is correct
4 Execution timed out 18056 ms 986784 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 14662 ms 290420 KB Output is correct
2 Correct 16470 ms 325136 KB Output is correct
3 Correct 7477 ms 264492 KB Output is correct
4 Execution timed out 18056 ms 986784 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2304 KB Output is correct
2 Correct 17 ms 1176 KB Output is correct
3 Correct 16 ms 1904 KB Output is correct
4 Correct 45 ms 2552 KB Output is correct
5 Correct 39 ms 2860 KB Output is correct
6 Correct 11 ms 2432 KB Output is correct
7 Correct 14156 ms 142636 KB Output is correct
8 Correct 13354 ms 142452 KB Output is correct
9 Correct 12760 ms 144044 KB Output is correct
10 Correct 13887 ms 304476 KB Output is correct
11 Execution timed out 18122 ms 406224 KB Time limit exceeded
12 Halted 0 ms 0 KB -