oj.uz

Submission #395687

# Submission time Handle Problem Language Result Execution time Memory
395687 2021-04-28T18:19:55 Z MrRobot_28 Specijacija (COCI20_specijacija) C++17
20 / 110
 4000 ms 141600 KB 
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define sz(a) (int)a.size()
#define ll long long
const int N = 3e5;
const int T = 20;
int n, m, t;
ll mod;
ll 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(ll a)
{
    int l = -1, r = n;
    while(r - l > 1)
    {
        ll midd = (r + l) / 2;
        if((midd + 2) * (midd + 1) / 2 <= a)
        {
            l = midd;
        }
        else
        {
            r = midd;
        }
    }
    return {l + 1, a - 1LL * (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 t2 = go_to2(v -> right, (r + l) / 2 + 1, r, x);
    if(t2 != -1)
    {
        return t2;
    }
    int t1 = go_to2(v -> left, l, (r + l) / 2, x);
    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);
}
ll query(ll a, ll 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 + 1LL * (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()
{
  //  ifstream cin("input1.txt.4c");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> t;
   // cout << n << "\n";
    mod = 1LL * (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] -= 1LL * i * (i + 1) / 2;
        int u = go_to(mass[i + 1], 0, n, a[i]);
        mass[i] = new node();
        go_to1(mass[i + 1], mass[i], 0, n, u);
    }
    ll z = 0;
    for(int i = 0; i < m; i++)
    {
        ll a, b;
        cin >>  a >> b;
        a = (a - 1 + 1LL * t * z) % mod;
        b = (b - 1 + 1LL * t * z) % mod;
        cout << (z = query(a, b)) << "\n";
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 133060 KB Output is correct
2 Correct 21 ms 10068 KB Output is correct
3 Correct 369 ms 132964 KB Output is correct
4 Correct 181 ms 69480 KB Output is correct
5 Correct 372 ms 132948 KB Output is correct
6 Correct 98 ms 39396 KB Output is correct
7 Correct 244 ms 132932 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 133060 KB Output is correct
2 Correct 21 ms 10068 KB Output is correct
3 Correct 369 ms 132964 KB Output is correct
4 Correct 181 ms 69480 KB Output is correct
5 Correct 372 ms 132948 KB Output is correct
6 Correct 98 ms 39396 KB Output is correct
7 Correct 244 ms 132932 KB Output is correct
8 Correct 446 ms 1192 KB Output is correct
9 Correct 366 ms 984 KB Output is correct
10 Correct 466 ms 1272 KB Output is correct
11 Correct 246 ms 748 KB Output is correct
12 Correct 447 ms 1148 KB Output is correct
13 Correct 309 ms 968 KB Output is correct
14 Correct 537 ms 1672 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 133060 KB Output is correct
2 Correct 21 ms 10068 KB Output is correct
3 Correct 369 ms 132964 KB Output is correct
4 Correct 181 ms 69480 KB Output is correct
5 Correct 372 ms 132948 KB Output is correct
6 Correct 98 ms 39396 KB Output is correct
7 Correct 244 ms 132932 KB Output is correct
8 Correct 446 ms 1192 KB Output is correct
9 Correct 366 ms 984 KB Output is correct
10 Correct 466 ms 1272 KB Output is correct
11 Correct 246 ms 748 KB Output is correct
12 Correct 447 ms 1148 KB Output is correct
13 Correct 309 ms 968 KB Output is correct
14 Correct 537 ms 1672 KB Output is correct
15 Correct 3634 ms 135896 KB Output is correct
16 Correct 2055 ms 30268 KB Output is correct
17 Correct 3669 ms 140096 KB Output is correct
18 Correct 2055 ms 31140 KB Output is correct
19 Correct 3694 ms 140276 KB Output is correct
20 Correct 1975 ms 27732 KB Output is correct
21 Execution timed out 4086 ms 141600 KB Time limit exceeded

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3675 ms 134980 KB Output is correct
2 Correct 2812 ms 68028 KB Output is correct
3 Correct 3699 ms 140388 KB Output is correct
4 Correct 2827 ms 65864 KB Output is correct
5 Correct 3638 ms 140420 KB Output is correct
6 Correct 2898 ms 73892 KB Output is correct
7 Execution timed out 4072 ms 141456 KB Time limit exceeded