oj.uz

Submission #395685

# Submission time Handle Problem Language Result Execution time Memory
395685 2021-04-28T18:17:22 Z MrRobot_28 Specijacija (COCI20_specijacija) C++17
20 / 110
 4000 ms 133256 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 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);
}
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 388 ms 132892 KB Output is correct
2 Correct 22 ms 10060 KB Output is correct
3 Correct 394 ms 133032 KB Output is correct
4 Correct 192 ms 69528 KB Output is correct
5 Correct 386 ms 132980 KB Output is correct
6 Correct 100 ms 39492 KB Output is correct
7 Correct 247 ms 133060 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 132892 KB Output is correct
2 Correct 22 ms 10060 KB Output is correct
3 Correct 394 ms 133032 KB Output is correct
4 Correct 192 ms 69528 KB Output is correct
5 Correct 386 ms 132980 KB Output is correct
6 Correct 100 ms 39492 KB Output is correct
7 Correct 247 ms 133060 KB Output is correct
8 Correct 667 ms 1264 KB Output is correct
9 Correct 549 ms 1016 KB Output is correct
10 Correct 698 ms 1276 KB Output is correct
11 Correct 310 ms 696 KB Output is correct
12 Correct 659 ms 1284 KB Output is correct
13 Correct 400 ms 836 KB Output is correct
14 Correct 644 ms 1760 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 132892 KB Output is correct
2 Correct 22 ms 10060 KB Output is correct
3 Correct 394 ms 133032 KB Output is correct
4 Correct 192 ms 69528 KB Output is correct
5 Correct 386 ms 132980 KB Output is correct
6 Correct 100 ms 39492 KB Output is correct
7 Correct 247 ms 133060 KB Output is correct
8 Correct 667 ms 1264 KB Output is correct
9 Correct 549 ms 1016 KB Output is correct
10 Correct 698 ms 1276 KB Output is correct
11 Correct 310 ms 696 KB Output is correct
12 Correct 659 ms 1284 KB Output is correct
13 Correct 400 ms 836 KB Output is correct
14 Correct 644 ms 1760 KB Output is correct
15 Execution timed out 4074 ms 133256 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 4085 ms 133256 KB Time limit exceeded
2 Halted 0 ms 0 KB -