Submission #396079

#	Time	Username	Problem	Language	Result	Execution time	Memory
396079		MrRobot_28	Specijacija (COCI20_specijacija)	C++17	20 / 110	4081 ms	211896 KiB

Main

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60