oj.uz

Submission #396081

# Submission time Handle Problem Language Result Execution time Memory
396081 2021-04-29T12:27:51 Z MrRobot_28 Specijacija (COCI20_specijacija) C++17
110 / 110
 2079 ms 218564 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;
        cout << (z = query(a, b)) << "\n";
    }
  //  cout << "A";
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 717 ms 202436 KB Output is correct
2 Correct 50 ms 33292 KB Output is correct
3 Correct 722 ms 202372 KB Output is correct
4 Correct 378 ms 115852 KB Output is correct
5 Correct 725 ms 202352 KB Output is correct
6 Correct 209 ms 74556 KB Output is correct
7 Correct 504 ms 209888 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 717 ms 202436 KB Output is correct
2 Correct 50 ms 33292 KB Output is correct
3 Correct 722 ms 202372 KB Output is correct
4 Correct 378 ms 115852 KB Output is correct
5 Correct 725 ms 202352 KB Output is correct
6 Correct 209 ms 74556 KB Output is correct
7 Correct 504 ms 209888 KB Output is correct
8 Correct 237 ms 20232 KB Output is correct
9 Correct 204 ms 19916 KB Output is correct
10 Correct 240 ms 20364 KB Output is correct
11 Correct 167 ms 19632 KB Output is correct
12 Correct 241 ms 20236 KB Output is correct
13 Correct 190 ms 19792 KB Output is correct
14 Correct 238 ms 20868 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 717 ms 202436 KB Output is correct
2 Correct 50 ms 33292 KB Output is correct
3 Correct 722 ms 202372 KB Output is correct
4 Correct 378 ms 115852 KB Output is correct
5 Correct 725 ms 202352 KB Output is correct
6 Correct 209 ms 74556 KB Output is correct
7 Correct 504 ms 209888 KB Output is correct
8 Correct 237 ms 20232 KB Output is correct
9 Correct 204 ms 19916 KB Output is correct
10 Correct 240 ms 20364 KB Output is correct
11 Correct 167 ms 19632 KB Output is correct
12 Correct 241 ms 20236 KB Output is correct
13 Correct 190 ms 19792 KB Output is correct
14 Correct 238 ms 20868 KB Output is correct
15 Correct 2062 ms 204104 KB Output is correct
16 Correct 1092 ms 59984 KB Output is correct
17 Correct 2052 ms 209640 KB Output is correct
18 Correct 1114 ms 60924 KB Output is correct
19 Correct 2070 ms 209512 KB Output is correct
20 Correct 1044 ms 56408 KB Output is correct
21 Correct 1924 ms 218564 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2060 ms 203692 KB Output is correct
2 Correct 1524 ms 111788 KB Output is correct
3 Correct 2079 ms 209740 KB Output is correct
4 Correct 1561 ms 108884 KB Output is correct
5 Correct 2040 ms 209604 KB Output is correct
6 Correct 1579 ms 119768 KB Output is correct
7 Correct 1927 ms 218456 KB Output is correct