Submission #1089894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089894		SalihSahin	Specijacija (COCI20_specijacija)	C++14	20 / 110	4056 ms	11860 KiB

Main

#include<bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;

const int mod = 1e9 + 7;
const int inf = 1e9;
const int N = 2e5 + 5;

 vector<int> a(N), dpg(N);

 int go_par(int x, int depx){
  if(x <= 3) return 1;
  return (x - (depx - 1 + ((a[depx-1] - dpg[depx-1]) < (x - dpg[depx]))));
 }

int find_dep(int x){
  int l = 1, r = N;

  while(l < r){
    int m = (l + r)/2;

    if(x <= m * (m + 1) / 2) r = m;
    else l = m + 1;
  }

  return l;
}

int32_t main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n, q, t;
  cin>>n>>q>>t;
  for(int i = 1; i <= n; i++){
    cin>>a[i];
  }
  for(int i = 1; i <= n+2; i++){
    dpg[i] = i * (i - 1) / 2;
  }

  vector<int> x(q+1), y(q+1), z(q+1);
  for(int i = 1; i <= q; i++){
    cin>>x[i]>>y[i];
    int u = (x[i] - 1 + t * z[i-1]) % ((n+1) * (n+2) / 2) + 1;
    int v = (y[i] - 1 + t * z[i-1]) % ((n+1) * (n+2) / 2) + 1;
    int depu = find_dep(u), depv = find_dep(v);

    while(depv > depu){
      v = go_par(v, depv);
      depv--;
    }
    while(depu > depv){
      u = go_par(u, depu);
      depu--;
    }

    while(u != v){
      v = go_par(v, depv);
      u = go_par(u, depu);
      depu--;
      depv--;
    }

    cout<<u<<endl;
    z[i] = u;
  }
  return 0;
}

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