oj.uz

Submission #396079

# Submission time Handle Problem Language Result Execution time Memory
396079 2021-04-29T12:27:19 Z MrRobot_28 Specijacija (COCI20_specijacija) C++17
20 / 110
 4000 ms 211896 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 = 4e5 + 100;
const int T = 20;
int n, m, t;
ll mod;
ll a[N];
int lca[N][T];
int up[N];
int vals[N];
int H[N];
int idx[N];
vector <pair <int, int> > vec[N];
vector <int> g[N];
int it = 2e5;
struct node{
    node* left;
    node* right;
    int _sz;
    node(){};
};
void dfs(int v)
{
    for(auto to : g[v])
    {
        H[to] = H[v] + 1;
        dfs(to);
    }
}
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 query1(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;
}

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);
    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);
    //cout << t.X << " " << t.Y << " " << t1.X << " " << t1.Y << "\n";
    int f1 = lower_bound(vec[t.Y].begin(), vec[t.Y].end(), make_pair(t.X, 0)) - vec[t.Y].begin();
    t.Y = vec[t.Y][f1].Y;
    f1 = lower_bound(vec[t1.Y].begin(), vec[t1.Y].end(), make_pair(t.X, 0)) - vec[t1.Y].begin();
    t1.Y = vec[t1.Y][f1].Y;
  //  cout << t.X << " " << t.Y << " " << t1.X << " " << t1.Y << "\n";
    if(t.Y == t1.Y)
    {
        t.Y = coun(mass[t.X], 0, n, idx[t.Y] - 1);
        return t.Y + 1 + 1LL * t.X * (t.X + 1) / 2;
    }

    if(H[t.Y] > H[t1.Y])
    {
        swap(t, t1);
    }
    int len = H[t1.Y] - H[t.Y];
    for(int j = T - 1; j >= 0; j--)
    {
        if((1 << j ) <= len)
        {
            len -= (1 << j);
            t1.Y = lca[t1.Y][j];
        }
    }
  //  cout << t.Y << " " << t1.Y << "\n";
    for(int i = T - 1; i >= 0; i--)
    {
        if(lca[t1.Y][i] == lca[t.Y][i])
        {
            continue;
        }
        t1.Y = lca[t1.Y][i];
        t.Y = lca[t.Y][i];
    }

    t1.Y = lca[t1.Y][0];
    //cout << t1.Y << "\n";
    t.X = up[t1.Y];
  //  cout << t.X << "\n";
    t.Y = coun(mass[t.X], 0, n, idx[t1.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++)
    {
        //a[i] = rand() % (i + 1) + 1;
        //a[i] += i * (i + 1) / 2;
   //     cout << a[i] << " ";
        cin >> a[i];
    }
  //  cout << "\n";
    mass[n] = new node();
    build(mass[n], 0, n);
    //cout << "A\n";
    lca[0][0] = 0;
    up[0] = -1;
    for(int i = 0; i <= n; i++)
    {
        vals[i] = i;
        idx[i] = i;
        up[i] = n;
        vec[i].push_back({n, i});
    }
    it = n;
    for(int i = n - 1; i >= 0; i--)
    {
        a[i] -= 1LL * i * (i + 1) / 2;
        int u1 =go_to(mass[i + 1], 0, n, a[i] - 1);
        int u = go_to(mass[i + 1], 0, n, a[i]);
        vec[u1].push_back({i, it + 1});
        idx[it + 1] = u1;
        g[it + 1].push_back(vals[u]);
        g[it + 1].push_back(vals[u1]);
        lca[vals[u]][0] = it + 1;
        lca[vals[u1]][0] = it + 1;
        up[it + 1] = i;
        vals[u1] = ++it;
        mass[i] = new node();
        go_to1(mass[i + 1], mass[i], 0, n, u);
    }
    for(int i = 0; i <= n; i++)
    {
        sort(vec[i].begin(), vec[i].end());
    }
    dfs(it);
    for(int j = 1; j < T; j++)
    {
        for(int i = 0; i <= n * 2; i++)
        {
            lca[i][j] = lca[lca[i][j - 1]][j - 1];
        }
    }
    ll z = 0;
    for(int i = 0; i < m; i++)
    {
        ll a, b;
        cin >>  a >> b;
        //a = rand() % mod + 1;
        //b = rand() % mod + 1;
        a = (a - 1 + 1LL * t * z) % mod;
        b = (b - 1 + 1LL * t * z) % mod;
        if(query(a, b) != query1(a, b))
        {
            assert(0);
        }
        cout << (z = query(a, b)) << "\n";
    }
  //  cout << "A";
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 731 ms 204520 KB Output is correct
2 Correct 50 ms 33476 KB Output is correct
3 Correct 752 ms 204416 KB Output is correct
4 Correct 379 ms 117060 KB Output is correct
5 Correct 736 ms 204476 KB Output is correct
6 Correct 201 ms 75200 KB Output is correct
7 Correct 503 ms 211896 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 731 ms 204520 KB Output is correct
2 Correct 50 ms 33476 KB Output is correct
3 Correct 752 ms 204416 KB Output is correct
4 Correct 379 ms 117060 KB Output is correct
5 Correct 736 ms 204476 KB Output is correct
6 Correct 201 ms 75200 KB Output is correct
7 Correct 503 ms 211896 KB Output is correct
8 Correct 754 ms 23024 KB Output is correct
9 Correct 631 ms 22404 KB Output is correct
10 Correct 787 ms 22928 KB Output is correct
11 Correct 462 ms 21572 KB Output is correct
12 Correct 788 ms 23060 KB Output is correct
13 Correct 590 ms 21896 KB Output is correct
14 Correct 879 ms 23488 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 731 ms 204520 KB Output is correct
2 Correct 50 ms 33476 KB Output is correct
3 Correct 752 ms 204416 KB Output is correct
4 Correct 379 ms 117060 KB Output is correct
5 Correct 736 ms 204476 KB Output is correct
6 Correct 201 ms 75200 KB Output is correct
7 Correct 503 ms 211896 KB Output is correct
8 Correct 754 ms 23024 KB Output is correct
9 Correct 631 ms 22404 KB Output is correct
10 Correct 787 ms 22928 KB Output is correct
11 Correct 462 ms 21572 KB Output is correct
12 Correct 788 ms 23060 KB Output is correct
13 Correct 590 ms 21896 KB Output is correct
14 Correct 879 ms 23488 KB Output is correct
15 Execution timed out 4056 ms 208488 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 4081 ms 208760 KB Time limit exceeded
2 Halted 0 ms 0 KB -