test/aoj/0425.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 10:56:39+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Final/0425

Depends on

• Mo's Algorithm (src/Misc/Mo.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Final/0425
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <numeric>
#include <algorithm>
#include "src/Misc/Mo.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, K, Q;
 cin >> N >> K >> Q;
 int a[K], b[K];
 for (int k= 0; k < K; k++) cin >> a[k] >> b[k], a[k]--, b[k]--;
 Mo mo;
 int op[Q], x[Q];
 for (int q= 0; q < Q; q++) {
  int s, t;
  cin >> op[q] >> s >> t >> x[q], x[q]--;
  mo.query(--s, t);
 }
 int ord[N], pos[N];
 iota(ord, ord + N, 0), iota(pos, pos + N, 0);
 auto mover= [&](int k) { swap(ord[a[k]], ord[b[k]]), swap(pos[ord[a[k]]], pos[ord[b[k]]]); };
 auto movel= [&](int k) { swap(pos[a[k]], pos[b[k]]), swap(ord[pos[a[k]]], ord[pos[b[k]]]); };
 int ans[Q];
 auto out= [&](int q) { ans[q]= (op[q] == 1 ? ord[x[q]] : pos[x[q]]) + 1; };
 mo.run(movel, mover, movel, mover, out);
 for (int q= 0; q < Q; q++) cout << ans[q] << "\n";
 return 0;
}

#line 1 "test/aoj/0425.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Final/0425
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <numeric>
#include <algorithm>
#line 2 "src/Misc/Mo.hpp"
#include <vector>
#line 5 "src/Misc/Mo.hpp"
#include <cmath>
struct Mo {
 std::vector<int> L, R;
 Mo() {}
 void query(int l, int r) { L.push_back(l), R.push_back(r); } /* [l, r) */
 template <typename AL, typename AR, typename EL, typename ER, typename O> void run(const AL &add_left, const AR &add_right, const EL &erase_left, const ER &erase_right, const O &out) {
  int q= L.size(), n= *std::max_element(R.begin(), R.end()), bs= n / std::min<int>(n, std::sqrt(q));
  std::vector<int> ord(q);
  std::iota(ord.begin(), ord.end(), 0), std::sort(ord.begin(), ord.end(), [&](int a, int b) {
   int ablk= L[a] / bs, bblk= L[b] / bs;
   return ablk != bblk ? ablk < bblk : (ablk & 1) ? R[a] > R[b] : R[a] < R[b];
  });
  int l= 0, r= 0;
  for (auto i: ord) {
   while (l > L[i]) add_left(--l);
   while (r < R[i]) add_right(r++);
   while (l < L[i]) erase_left(l++);
   while (r > R[i]) erase_right(--r);
   out(i);
  }
 }
 template <typename A, typename E, typename O> void run(const A &add, const E &erase, const O &out) { run(add, add, erase, erase, out); }
};
#line 8 "test/aoj/0425.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, K, Q;
 cin >> N >> K >> Q;
 int a[K], b[K];
 for (int k= 0; k < K; k++) cin >> a[k] >> b[k], a[k]--, b[k]--;
 Mo mo;
 int op[Q], x[Q];
 for (int q= 0; q < Q; q++) {
  int s, t;
  cin >> op[q] >> s >> t >> x[q], x[q]--;
  mo.query(--s, t);
 }
 int ord[N], pos[N];
 iota(ord, ord + N, 0), iota(pos, pos + N, 0);
 auto mover= [&](int k) { swap(ord[a[k]], ord[b[k]]), swap(pos[ord[a[k]]], pos[ord[b[k]]]); };
 auto movel= [&](int k) { swap(pos[a[k]], pos[b[k]]), swap(ord[pos[a[k]]], ord[pos[b[k]]]); };
 int ans[Q];
 auto out= [&](int q) { ans[q]= (op[q] == 1 ? ord[x[q]] : pos[x[q]]) + 1; };
 mo.run(movel, mover, movel, mover, out);
 for (int q= 0; q < Q; q++) cout << ans[q] << "\n";
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	00_sample_00.in	AC	6 ms	4 MB
g++-13	04_rand_00.in	AC	5 ms	4 MB
g++-13	04_rand_01.in	AC	5 ms	4 MB
g++-13	04_rand_02.in	AC	5 ms	4 MB
g++-13	04_rand_03.in	AC	5 ms	4 MB
g++-13	05_large_00.in	AC	5 ms	4 MB
g++-13	05_large_01.in	AC	5 ms	4 MB
g++-13	05_large_02.in	AC	12 ms	4 MB
g++-13	06_maximum_00.in	AC	169 ms	7 MB
g++-13	10_small_01.in	AC	6 ms	4 MB
g++-13	10_small_02.in	AC	5 ms	4 MB
g++-13	10_small_03.in	AC	5 ms	4 MB
g++-13	10_small_04.in	AC	5 ms	4 MB
g++-13	20_mid_01.in	AC	5 ms	4 MB
g++-13	20_mid_02.in	AC	5 ms	4 MB
g++-13	20_mid_03.in	AC	5 ms	4 MB
g++-13	20_mid_04.in	AC	5 ms	4 MB
g++-13	30_large_01.in	AC	11 ms	4 MB
g++-13	30_large_02.in	AC	9 ms	4 MB
g++-13	30_large_03.in	AC	9 ms	4 MB
g++-13	30_large_04.in	AC	8 ms	4 MB
g++-13	40_max_01.in	AC	169 ms	7 MB
g++-13	40_max_02.in	AC	172 ms	7 MB
g++-13	40_max_03.in	AC	172 ms	7 MB
g++-13	40_max_04.in	AC	173 ms	7 MB
g++-13	40_max_05.in	AC	172 ms	7 MB
g++-13	40_max_longQ_01.in	AC	55 ms	7 MB
g++-13	40_max_longQ_02.in	AC	58 ms	7 MB
g++-13	40_max_shortQ_01.in	AC	61 ms	7 MB
g++-13	40_max_shortQ_02.in	AC	61 ms	7 MB
g++-13	50_beet_max_01.in	AC	66 ms	7 MB
g++-13	50_beet_max_02.in	AC	67 ms	7 MB
g++-13	50_beet_max_03.in	AC	56 ms	7 MB
g++-13	50_beet_max_04.in	AC	66 ms	7 MB
g++-13	50_beet_max_05.in	AC	62 ms	7 MB
clang++-18	00_sample_00.in	AC	6 ms	4 MB
clang++-18	04_rand_00.in	AC	5 ms	4 MB
clang++-18	04_rand_01.in	AC	5 ms	4 MB
clang++-18	04_rand_02.in	AC	5 ms	4 MB
clang++-18	04_rand_03.in	AC	5 ms	4 MB
clang++-18	05_large_00.in	AC	5 ms	4 MB
clang++-18	05_large_01.in	AC	5 ms	4 MB
clang++-18	05_large_02.in	AC	11 ms	4 MB
clang++-18	06_maximum_00.in	AC	165 ms	7 MB
clang++-18	10_small_01.in	AC	6 ms	4 MB
clang++-18	10_small_02.in	AC	5 ms	4 MB
clang++-18	10_small_03.in	AC	5 ms	4 MB
clang++-18	10_small_04.in	AC	5 ms	4 MB
clang++-18	20_mid_01.in	AC	5 ms	4 MB
clang++-18	20_mid_02.in	AC	5 ms	4 MB
clang++-18	20_mid_03.in	AC	5 ms	4 MB
clang++-18	20_mid_04.in	AC	5 ms	4 MB
clang++-18	30_large_01.in	AC	11 ms	4 MB
clang++-18	30_large_02.in	AC	9 ms	4 MB
clang++-18	30_large_03.in	AC	9 ms	4 MB
clang++-18	30_large_04.in	AC	7 ms	4 MB
clang++-18	40_max_01.in	AC	167 ms	7 MB
clang++-18	40_max_02.in	AC	173 ms	7 MB
clang++-18	40_max_03.in	AC	168 ms	7 MB
clang++-18	40_max_04.in	AC	169 ms	7 MB
clang++-18	40_max_05.in	AC	168 ms	7 MB
clang++-18	40_max_longQ_01.in	AC	54 ms	7 MB
clang++-18	40_max_longQ_02.in	AC	54 ms	7 MB
clang++-18	40_max_shortQ_01.in	AC	60 ms	7 MB
clang++-18	40_max_shortQ_02.in	AC	60 ms	7 MB
clang++-18	50_beet_max_01.in	AC	61 ms	7 MB
clang++-18	50_beet_max_02.in	AC	61 ms	7 MB
clang++-18	50_beet_max_03.in	AC	57 ms	7 MB
clang++-18	50_beet_max_04.in	AC	61 ms	7 MB
clang++-18	50_beet_max_05.in	AC	57 ms	7 MB

Back to top page