oj.uz

Submission #395673

# Submission time Handle Problem Language Result Execution time Memory
395673 2021-04-28T18:02:27 Z MrRobot_28 Specijacija (COCI20_specijacija) C++17
20 / 110
 4000 ms 137528 KB 
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define sz(a) (int)a.size()
#define int long long
const int N = 3e5;
const int T = 20;
int n, m, t;
int mod;
int a[N];
struct node{
    node* left;
    node* right;
    int _sz;
    node(){};
};
node* mass[N];
int go_to(node* v, int l, int r, int d)
{
    if(l == r)
    {
        return l;
    }
    if(v -> left -> _sz <= d)
    {
        return go_to(v -> right, (r + l) / 2 + 1, r, d - v -> left -> _sz);
    }
    return go_to(v -> left, l, (r + l) / 2, d);
}
void go_to1(node* pr, node *&v, int l, int r, int k)
{
    v -> _sz = pr -> _sz;
    v -> _sz--;
    if(l == r)
    {
        return;
    }
    if(k <= (r + l) / 2)
    {
        v -> left = new node();
        v -> right = pr -> right;
        go_to1(pr -> left, v -> left, l, (r + l) / 2, k);
    }
    else
    {
        v -> left = pr -> left;
        v -> right = new node();
        go_to1(pr -> right, v -> right, (r + l) / 2 + 1, r, k);
    }
}

pair <int, int> funct(int a)
{
    int l = -1, r = n;
    while(r - l > 1)
    {
        int midd = (r + l) / 2;
        if((midd + 2) * (midd + 1) / 2 <= a)
        {
            l = midd;
        }
        else
        {
            r = midd;
        }
    }
    return {l + 1, a - (l + 2) * (l + 1) / 2};
}
int go_to2(node* v, int l, int r, int x)
{
    if(!v -> _sz)
    {
        return -1;
    }
    if(l > x)
    {
        return -1;
    }
    if(l == r)
    {
        return l;
    }
    if(r <= x)
    {
        if(v -> right -> _sz)
        {
            return go_to2(v -> right, (r + l) / 2 + 1, r, x);
        }
        return go_to2(v -> left, l, (r + l) / 2, x);
    }
    int t1 = go_to2(v -> left, l, (r + l) / 2, x);
    int t2 = go_to2(v -> right, (r + l) / 2 + 1, r, x);
    if(t2 != -1)
    {
        return t2;
    }
    return t1;
}
int coun(node* v, int l, int r, int x)
{
    if(x < l)
    {
        return 0;
    }
    if(r <= x)
    {
        return v -> _sz;
    }
    return coun(v -> left, l, (r + l) / 2, x) + coun(v -> right, (r + l) / 2 + 1, r, x);
}
int query(int a, int b)
{
    pair <int, int> t = funct(a);
    pair <int, int> t1 = funct(b);
    t.Y = go_to(mass[t.X], 0, n, t.Y);
    t1.Y = go_to(mass[t1.X], 0, n, t1.Y);
 //   cout << t.X << " " << t.Y << " " << t1.X << " " << t1.Y << "\n";
    if(t.X > t1.X)
    {
        swap(t, t1);
    }
    t.Y = go_to2(mass[t.X], 0, n, t.Y);
    t1.Y = go_to2(mass[t.X], 0, n, t1.Y);
    for(int j = T - 1; j >= 0; j--)
    {
        if(t.Y == t1.Y)
        {
            break;
        }
 //       cout << j << "\n";
        if((1 << j) <= t.X && go_to2(mass[t.X - (1 << j)], 0, n, t.Y) != go_to2(mass[t.X - (1 << j)], 0, n, t1.Y))
        {
            t.Y = go_to2(mass[t.X - (1 << j)], 0, n, t.Y);
            t1.Y = go_to2(mass[t.X - (1 << j)], 0, n, t1.Y);
            t.X -= (1 << j);
        }
    }
   // cout << t.X << " " << t.Y << " " << t1.Y << "\n";
    if(t.Y != t1.Y)
    {
        t.X--;
        t.Y = go_to2(mass[t.X], 0, n, t.Y);
    }
    t.Y = coun(mass[t.X], 0, n, t.Y - 1);
    return t.Y + 1 + (t.X) * (t.X + 1) / 2;
}
void build(node* &v, int l, int r)
{
    v -> _sz = r - l + 1;
    if(l == r)
    {
        return;
    }
    v -> left = new node();
    v -> right = new node();
    build(v -> left, l, (r + l) / 2);
    build(v -> right, (r + l) / 2 + 1, r);
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> t;
    mod = (n + 1) * (n + 2) / 2;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    mass[n] = new node();
    build(mass[n], 0, n);
    //cout << "A\n";
    for(int i = n - 1; i >= 0; i--)
    {
        a[i] -= i * (i + 1) / 2;
        int u = go_to(mass[i + 1], 0, n, a[i]);
        mass[i] = new node();
       // cout << a[i] << " " << u << "\n";
        go_to1(mass[i + 1], mass[i], 0, n, u);
    }
    int z = 0;
    for(int i = 0; i < m; i++)
    {
        int a, b;
        cin >>  a >> b;
        a = (a - 1 + t * z) % mod;
        b = (b - 1 + t * z) % mod;
        //cout << a << " " << b << " ";
        cout << (z = query(a, b)) << "\n";
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 135096 KB Output is correct
2 Correct 21 ms 10204 KB Output is correct
3 Correct 381 ms 135160 KB Output is correct
4 Correct 193 ms 70656 KB Output is correct
5 Correct 376 ms 135124 KB Output is correct
6 Correct 101 ms 40140 KB Output is correct
7 Correct 252 ms 135116 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 135096 KB Output is correct
2 Correct 21 ms 10204 KB Output is correct
3 Correct 381 ms 135160 KB Output is correct
4 Correct 193 ms 70656 KB Output is correct
5 Correct 376 ms 135124 KB Output is correct
6 Correct 101 ms 40140 KB Output is correct
7 Correct 252 ms 135116 KB Output is correct
8 Correct 680 ms 3896 KB Output is correct
9 Correct 514 ms 3516 KB Output is correct
10 Correct 741 ms 3940 KB Output is correct
11 Correct 298 ms 2660 KB Output is correct
12 Correct 668 ms 3996 KB Output is correct
13 Correct 389 ms 3140 KB Output is correct
14 Correct 645 ms 4644 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 135096 KB Output is correct
2 Correct 21 ms 10204 KB Output is correct
3 Correct 381 ms 135160 KB Output is correct
4 Correct 193 ms 70656 KB Output is correct
5 Correct 376 ms 135124 KB Output is correct
6 Correct 101 ms 40140 KB Output is correct
7 Correct 252 ms 135116 KB Output is correct
8 Correct 680 ms 3896 KB Output is correct
9 Correct 514 ms 3516 KB Output is correct
10 Correct 741 ms 3940 KB Output is correct
11 Correct 298 ms 2660 KB Output is correct
12 Correct 668 ms 3996 KB Output is correct
13 Correct 389 ms 3140 KB Output is correct
14 Correct 645 ms 4644 KB Output is correct
15 Execution timed out 4091 ms 137528 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 4059 ms 137416 KB Time limit exceeded
2 Halted 0 ms 0 KB -