oj.uz

Submission #1089894

# Submission time Handle Problem Language Result Execution time Memory
1089894 2024-09-17T11:22:14 Z SalihSahin Specijacija (COCI20_specijacija) C++14
20 / 110
 4000 ms 11860 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5724 KB Output is correct
2 Correct 3 ms 3676 KB Output is correct
3 Correct 15 ms 5752 KB Output is correct
4 Correct 9 ms 4700 KB Output is correct
5 Correct 20 ms 5712 KB Output is correct
6 Correct 6 ms 4188 KB Output is correct
7 Correct 15 ms 5504 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5724 KB Output is correct
2 Correct 3 ms 3676 KB Output is correct
3 Correct 15 ms 5752 KB Output is correct
4 Correct 9 ms 4700 KB Output is correct
5 Correct 20 ms 5712 KB Output is correct
6 Correct 6 ms 4188 KB Output is correct
7 Correct 15 ms 5504 KB Output is correct
8 Correct 617 ms 11264 KB Output is correct
9 Correct 408 ms 11096 KB Output is correct
10 Correct 597 ms 11344 KB Output is correct
11 Correct 278 ms 10592 KB Output is correct
12 Correct 610 ms 11264 KB Output is correct
13 Correct 347 ms 10836 KB Output is correct
14 Correct 534 ms 11860 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5724 KB Output is correct
2 Correct 3 ms 3676 KB Output is correct
3 Correct 15 ms 5752 KB Output is correct
4 Correct 9 ms 4700 KB Output is correct
5 Correct 20 ms 5712 KB Output is correct
6 Correct 6 ms 4188 KB Output is correct
7 Correct 15 ms 5504 KB Output is correct
8 Correct 617 ms 11264 KB Output is correct
9 Correct 408 ms 11096 KB Output is correct
10 Correct 597 ms 11344 KB Output is correct
11 Correct 278 ms 10592 KB Output is correct
12 Correct 610 ms 11264 KB Output is correct
13 Correct 347 ms 10836 KB Output is correct
14 Correct 534 ms 11860 KB Output is correct
15 Execution timed out 4048 ms 10708 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4056 ms 10712 KB Time limit exceeded
2 Halted 0 ms 0 KB -