제출 #1305347

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305347		fangyj	Specijacija (COCI20_specijacija)	C++20	컴파일 에러	0 ms	0 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double lf;
typedef long double Lf;
typedef pair <int,int> pii;
typedef pair <ll, ll> pll;
const int MAXN = 200005;
const int MAXNODES = MAXN * 100;
const int LOG = 19;
const int offset = (1 << 18);
struct node {
  int x, left;
  node *l, *r;
  node() {
    left = x = 0;
    l = r = 0;
  }
  node(int _x, int _left, node* _l, node* _r) {
    x = _x;
    left = _left;
    l = _l;
    r = _r;
  }
};
int CNT;
node nodes[MAXNODES];
node* newNode() {
  assert(CNT < MAXNODES);
  nodes[CNT].l = nodes[CNT].r = &nodes[CNT];
  return &nodes[CNT++];
}
struct tournament {
  node *root[MAXN];

  tournament() {
    REP(i, MAXN) root[i] = newNode();
  }

  pii kth(node *cvor, int l, int r, int k) {
    if (l == r) {
      return mp(l, cvor->x); 
    }

    int mid = (l + r) / 2;
    if (cvor->l && cvor->l->left >= k) {
      return kth(cvor->l, l, mid, k);
    } else {
      return kth(cvor->r, mid + 1, r, k - cvor->l->left);
    }
  }

  node *update(node *cvor, int l, int r, int a, int x) {
    if (l > a || r < a) return cvor;
    if (l == r) {
      node *tmp = newNode();
      tmp->x = x;
      tmp->left = (x != 0);
      return tmp;
    }

    int mid = (l + r) / 2;
    node *left = update(cvor->l, l, mid, a, x);
    node *right = update(cvor->r, mid + 1, r, a, x);
    node *tmp = newNode();
    tmp->l = left;
    tmp->r = right;
    tmp->left = left->left + right->left;
    return tmp;
  }
};

tournament T;

struct Tree {
  int lca[LOG][MAXN * 2], dub[MAXN * 2];

  vector <int> E[MAXN * 2];

  void add(int a, int b) {
    E[a].pb(b);
    E[b].pb(a);
  }

  void dfs(int cvor, int par, int d) {
    dub[cvor] = d;
    for (auto &ncvor : E[cvor]) {
      if (ncvor == par) continue;
      lca[0][ncvor] = cvor;
      dfs(ncvor, cvor, d + 1);
    }
  }

  void init_lca() {
    FOR(i, 1, LOG) {
      REP(j, MAXN * 2) {
        lca[i][j] = lca[i - 1][lca[i - 1][j]];
      }
    }
  }

  int get_lca(int a, int b) {
    if (dub[a] < dub[b]) swap(a, b);
    for (int i = LOG - 1; i >= 0; i--) {
      if (dub[a] - (1 << i) >= dub[b]) {
        a = lca[i][a];
      }
    }
    if (a == b) return a;

    for (int i = LOG - 1; i >= 0; i--) {
      if (lca[i][a] != lca[i][b]) {
        a = lca[i][a];
        b = lca[i][b];
      }
    }
    return lca[0][a];
  }
}stablo;

int n, q;
ll p[MAXN], caca[MAXN * 2];

int find(ll x) {
  int lo = 1, hi = n + 1, mid;
  while (lo != hi) {
    mid = (lo + hi + 1) / 2;
    if ((ll)mid * (mid - 1) / 2 < x) lo = mid;
    else hi = mid - 1;
  }

  int lvl = lo;

  int ind = (int)(x - (ll)lvl * (lvl - 1)/2);
  auto t = T.kth(T.root[lvl], 0, offset - 1, ind);
  return t.second;
}

ll query(ll a, ll b) {
  int x = find(a);
  int y = find(b);
  int l = stablo.get_lca(x, y);
  return min(min(a, b), caca[l]);
}

int main() {
  int t;
  scanf("%d %d %d",&n,&q,&t);
  REP(i, n) {
    scanf("%lld",&p[i + 1]);
  }

  REP(i, n + 1) {
    caca[i + 1] = (ll)(n + 1) * n / 2 + i + 1;
    T.root[n + 1] = T.update(T.root[n + 1], 0, offset - 1, i + 1, i + 1);
  }

  int komp = n + 2;
  for (int i = n; i > 0; i--) {
    int ind = (int)(p[i] - (ll)i * (i - 1)/2);
    auto a = T.kth(T.root[i + 1], 0, offset - 1, ind);
    auto b = T.kth(T.root[i + 1], 0, offset - 1, ind + 1);
    stablo.add(a.second, komp);
    stablo.add(b.second, komp);
    caca[komp] = p[i];
    T.root[i] = T.update(T.root[i + 1], 0, offset - 1, a.first, komp++);
    T.root[i] = T.update(T.root[i], 0, offset - 1, b.first, 0);
  }

  stablo.dfs(komp - 1, -1, 0);
  stablo.init_lca();

  ll last = 0;
  ll N = (ll)(n + 1) * (n + 2) / 2;
  REP(i, q) {
    ll a, b;
    scanf("%lld %lld",&a,&b);
    ll A = (a - 1 + t * last) % N + 1;
    ll B = (b - 1 + t * last) % N + 1;
    ll ans = query(A, B);
    printf("%lld\n", ans);
    last = ans;
  }

  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In constructor 'tournament::tournament()':
Main.cpp:37:9: error: 'i' was not declared in this scope
   37 |     REP(i, MAXN) root[i] = newNode();
      |         ^
Main.cpp:37:5: error: 'REP' was not declared in this scope
   37 |     REP(i, MAXN) root[i] = newNode();
      |     ^~~
Main.cpp: In member function 'pii tournament::kth(node*, int, int, int)':
Main.cpp:42:14: error: 'mp' was not declared in this scope
   42 |       return mp(l, cvor->x);
      |              ^~
Main.cpp: In member function 'void Tree::add(int, int)':
Main.cpp:81:10: error: 'class std::vector<int>' has no member named 'pb'
   81 |     E[a].pb(b);
      |          ^~
Main.cpp:82:10: error: 'class std::vector<int>' has no member named 'pb'
   82 |     E[b].pb(a);
      |          ^~
Main.cpp: In member function 'void Tree::init_lca()':
Main.cpp:95:9: error: 'i' was not declared in this scope
   95 |     FOR(i, 1, LOG) {
      |         ^
Main.cpp:95:5: error: 'FOR' was not declared in this scope
   95 |     FOR(i, 1, LOG) {
      |     ^~~
Main.cpp: In function 'int main()':
Main.cpp:149:7: error: 'i' was not declared in this scope
  149 |   REP(i, n) {
      |       ^
Main.cpp:149:3: error: 'REP' was not declared in this scope
  149 |   REP(i, n) {
      |   ^~~
Main.cpp:148:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |   scanf("%d %d %d",&n,&q,&t);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~