oj.uz

Submission #366282

# Submission time Handle Problem Language Result Execution time Memory
366282 2021-02-13T19:05:27 Z model_code Specijacija (COCI20_specijacija) C++17
110 / 110
 2077 ms 542888 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 888 ms 529692 KB Output is correct
2 Correct 325 ms 510956 KB Output is correct
3 Correct 894 ms 529524 KB Output is correct
4 Correct 581 ms 520312 KB Output is correct
5 Correct 881 ms 529644 KB Output is correct
6 Correct 457 ms 515732 KB Output is correct
7 Correct 622 ms 540692 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 888 ms 529692 KB Output is correct
2 Correct 325 ms 510956 KB Output is correct
3 Correct 894 ms 529524 KB Output is correct
4 Correct 581 ms 520312 KB Output is correct
5 Correct 881 ms 529644 KB Output is correct
6 Correct 457 ms 515732 KB Output is correct
7 Correct 622 ms 540692 KB Output is correct
8 Correct 514 ms 509768 KB Output is correct
9 Correct 482 ms 509932 KB Output is correct
10 Correct 508 ms 509932 KB Output is correct
11 Correct 444 ms 509676 KB Output is correct
12 Correct 506 ms 509804 KB Output is correct
13 Correct 456 ms 509804 KB Output is correct
14 Correct 503 ms 510444 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 888 ms 529692 KB Output is correct
2 Correct 325 ms 510956 KB Output is correct
3 Correct 894 ms 529524 KB Output is correct
4 Correct 581 ms 520312 KB Output is correct
5 Correct 881 ms 529644 KB Output is correct
6 Correct 457 ms 515732 KB Output is correct
7 Correct 622 ms 540692 KB Output is correct
8 Correct 514 ms 509768 KB Output is correct
9 Correct 482 ms 509932 KB Output is correct
10 Correct 508 ms 509932 KB Output is correct
11 Correct 444 ms 509676 KB Output is correct
12 Correct 506 ms 509804 KB Output is correct
13 Correct 456 ms 509804 KB Output is correct
14 Correct 503 ms 510444 KB Output is correct
15 Correct 2077 ms 530172 KB Output is correct
16 Correct 1278 ms 514124 KB Output is correct
17 Correct 2054 ms 530164 KB Output is correct
18 Correct 1295 ms 514260 KB Output is correct
19 Correct 2060 ms 530288 KB Output is correct
20 Correct 1236 ms 513876 KB Output is correct
21 Correct 1890 ms 542576 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2041 ms 530180 KB Output is correct
2 Correct 1584 ms 519756 KB Output is correct
3 Correct 2043 ms 530128 KB Output is correct
4 Correct 1649 ms 519396 KB Output is correct
5 Correct 2050 ms 530020 KB Output is correct
6 Correct 1710 ms 520616 KB Output is correct
7 Correct 1948 ms 542888 KB Output is correct