oj.uz

Submission #257621

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

struct info {
  int t, p, q;
  int idx;
  info () {}
};
info index(int i) {
  info x;
  x.t = 4;
  x.idx = i;
  return x;
}
struct ds {
  map <int, vector <int>> coord;
  map <int, int> value, par;
  ds () {}
  int root(int x) {
    if(par.find(x) == par.end() || 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) {
      par[y] = x;
    }
  }
  void add(int pos, int idx) {
    coord[pos].push_back(idx);
    value[idx] = pos;
    int parent = root(coord[pos].front());
    par[idx] = parent;
  }
  void join(int x, int y) {
    if(x == y || coord[y].empty()) return ;
    if(coord[x].size()) {
      joinIdx(coord[x].front(), coord[y].front());
    }
    if(coord[x].size() < coord[y].size()) {
      coord[x].swap(coord[y]);
    }
    for(int i : coord[y]) {
      coord[x].push_back(i);
    }
    value[root(coord[x].front())] = x;
    coord.erase(y);
  }
  int getPos(int idx) {
    return value[root(idx)];
  }
  vector <int> getIndex(int pos) {
    vector <int> ans;
    vector <int> del;
    for(auto i : coord) {
      if(i.first <= pos) {
        for(auto j : i.second) ans.push_back(j);
        del.push_back(i.first);
      }
    }
    for(auto i : del) {
      coord.erase(i);
    }
    return ans;
  }
  void move(int pos) {
    vector <int> del;
    for(auto i : coord) {
      if(i.first <= pos) {
        del.push_back(i.first);
      }
    }
    for(auto i : del) {
      join(pos, i);
    }
  }
}; 

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);
      }
    }
  }
  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);
  }
  solve(0, 0, v);
  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:153: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:159: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:164:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &add.t);
     ~~~~~^~~~~~~~~~~~~~
sweeping.cpp:166:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &add.p);
       ~~~~~^~~~~~~~~~~~~~
sweeping.cpp:169: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:170: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:173: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 40 ms 2248 KB Output is correct
2 Correct 21 ms 1232 KB Output is correct
3 Correct 12 ms 2048 KB Output is correct
4 Correct 38 ms 2304 KB Output is correct
5 Correct 40 ms 2688 KB Output is correct
6 Correct 10 ms 1792 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16542 ms 222768 KB Output is correct
2 Correct 16306 ms 222808 KB Output is correct
3 Correct 16373 ms 223352 KB Output is correct
4 Execution timed out 18075 ms 169496 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14225 ms 316640 KB Output is correct
2 Correct 14852 ms 350488 KB Output is correct
3 Execution timed out 18088 ms 187836 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 14225 ms 316640 KB Output is correct
2 Correct 14852 ms 350488 KB Output is correct
3 Execution timed out 18088 ms 187836 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2248 KB Output is correct
2 Correct 21 ms 1232 KB Output is correct
3 Correct 12 ms 2048 KB Output is correct
4 Correct 38 ms 2304 KB Output is correct
5 Correct 40 ms 2688 KB Output is correct
6 Correct 10 ms 1792 KB Output is correct
7 Correct 16542 ms 222768 KB Output is correct
8 Correct 16306 ms 222808 KB Output is correct
9 Correct 16373 ms 223352 KB Output is correct
10 Execution timed out 18075 ms 169496 KB Time limit exceeded
11 Halted 0 ms 0 KB -