Submission #366282

#	Time	Username	Problem	Language	Result	Execution time	Memory
366282		model_code	Specijacija (COCI20_specijacija)	C++17	110 / 110	2077 ms	542888 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;

#define TRACE(x) cerr << #x << "  " << x << endl
#define FOR(i, a, b) for (int i = (a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define _ << " " <<

#define fi first
#define sec second
#define mp make_pair
#define pb push_back

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;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:165:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  165 |   scanf("%d %d %d",&n,&q,&t);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp:167:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  167 |     scanf("%lld",&p[i + 1]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:194:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  194 |     scanf("%lld %lld",&a,&b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60