Submission #379756

# Submission time Handle Problem Language Result Execution time Memory
379756 2021-03-19T08:43:20 Z ne4eHbKa Specijacija (COCI20_specijacija) C++17
10 / 110
1879 ms 155948 KB
#include <bits/stdc++.h>
using namespace std;
#ifndef _LOCAL
//#pragma GCC optimize("O3,Ofast")
#else
#pragma GCC optimize("O0")
#endif
template<typename t> inline void umin(t &a, const t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, const t b) {a = max(a, b);}
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
typedef int8_t byte;
ll time() {return chrono::system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
#define ft first
#define sd second
#define len(f) int((f).size())
#define bnd(f) (f).begin(), (f).end()
#define _ <<' '<<
#define int ll
const int inf = 1e9 + 5;
const ll inf64 = 4e18 + 5;
const int md = 998244353;
namespace MD {
    void add(int &a, const int b) {if((a += b) >= md) a -= md;}
    void sub(int &a, const int b) {if((a -= b) < 0) a += md;}
    int prod(const int a, const int b) {return ll(a) * b % md;}
};

int n, q, T;
const int N = 2e5 + 5;
ll a[N], b[N], t[N], z;

struct tree {
    tree *l, *r;
    int v;
    tree(int tl = 0, int tr = n - 1) {
        if(tl < 0) {
            l = r = 0;
            v = 0;
        } else if(tl < tr) {
            int tm = tl + tr >> 1;
            l = new tree(tl, tm);
            r = new tree(tm + 1, tr);
            v = l->v + r->v;
        } else {
            l = r = 0;
            v = 1;
        }
    }
    tree(tree *f) {memcpy(this, f, sizeof *f);}
    tree *upd(int i, int tl = 0, int tr = n - 1) {
        if(tl == tr) return new tree(-1);
        int tm = tl + tr >> 1;
        tree *res = new tree(this);
        if(i <= tm)
            res->l = l->upd(i, tl, tm);
        else
            res->r = r->upd(i, tm + 1, tr);
        res->v--;
        return res;
    }
    int kth(int k, int tl = 0, int tr = n - 1) {
        if(tl == tr) return tl;
        int tm = tl + tr >> 1;
        return l->v > k
            ? l->kth(k, tl, tm)
            : r->kth(k - l->v, tm + 1, tr);
    }
    int sum(int R, int tl = 0, int tr = n - 1) {
        if(tr <= R) return v;
        if(tl > R) return 0;
        int tm = tl + tr >> 1;
        return l->sum(R, tl, tm) +
               r->sum(R, tm + 1, tr);
    }
};

vector<tree*> p;

void get(ll &x, int &i, int &j) {
    cin >> x;
    x = 1 + (x - 1 + T * z) % ((n + 1) * ll(n) >> 1);
    i = upper_bound(b, b + n, x) - b - 1;
    j = p[i]->kth(x - b[i]);
}

struct tree2 {
    tree2 *l, *r;
    int v;
    tree2(int tl = 0, int tr = n - 2) {
        if(tl < tr) {
            int tm = tl + tr >> 1;
            l = new tree2(tl, tm);
            r = new tree2(tm + 1, tr);
            v = min(l->v, r->v);
        } else {
            l = r = 0;
            v = t[tl];
        }
    }
    int get(int L, int R, int tl = 0, int tr = n - 2) {
        if(L > R) return +inf;
        if(L == tl && R == tr) return v;
        int tm = tl + tr >> 1;
        return min(l->get(L, min(R, tm), tl, tm),
                   r->get(max(tm + 1, L), R, tm + 1, tr));
    }
};

void solve() {
    cin >> n >> q >> T; ++n;
    for(ll i = 0, j = 1; i < n - 1; ++i) {
        j += i;
        cin >> a[i];
        a[i] -= j;
        b[i] = j;
    }
    b[n - 1] = n * ll(n - 1) / 2 + 1;
    p.assign(1, new tree());
    for(int i = n - 2; ~i; --i) {
        tree *rt = p.back();
        int c = rt->kth(a[i]);
        p.push_back(rt = rt->upd(c));
        t[c] = i;
    }
    tree2 tt {};
    reverse(bnd(p));
    z = 0;
    for(int i = 0; i < q; ++i) {
        ll x, y;
        int ix, iy, jx, jy;
        get(x, ix, jx);
        get(y, iy, jy);
        if(jx == jy) {
            z = ix < iy ? x : y;
        } else {
            if(jx > jy) swap(jx, jy),
                        swap(ix, iy),
                        swap(x, y);
            int v = tt.get(jx, jy - 1);
            z = b[v] + p[v]->sum(jx);
        }
        cout << z << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifndef _LOCAL
//    freopen("file.in", "r", stdin);
//    freopen("file.out", "w", stdout);
#else
    system("color a");
    freopen("in.txt", "r", stdin);
    int t; cin >> t;
    while(t--)
#endif
    solve();
}

Compilation message

Main.cpp: In constructor 'tree::tree(ll, ll)':
Main.cpp:43:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |             int tm = tl + tr >> 1;
      |                      ~~~^~~~
Main.cpp: In member function 'tree* tree::upd(ll, ll, ll)':
Main.cpp:55:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |         int tm = tl + tr >> 1;
      |                  ~~~^~~~
Main.cpp: In member function 'll tree::kth(ll, ll, ll)':
Main.cpp:66:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |         int tm = tl + tr >> 1;
      |                  ~~~^~~~
Main.cpp: In member function 'll tree::sum(ll, ll, ll)':
Main.cpp:74:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |         int tm = tl + tr >> 1;
      |                  ~~~^~~~
Main.cpp: In constructor 'tree2::tree2(ll, ll)':
Main.cpp:94:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |             int tm = tl + tr >> 1;
      |                      ~~~^~~~
Main.cpp: In member function 'll tree2::get(ll, ll, ll, ll)':
Main.cpp:106:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |         int tm = tl + tr >> 1;
      |                  ~~~^~~~
# Verdict Execution time Memory Grader output
1 Correct 489 ms 150800 KB Output is correct
2 Correct 26 ms 11624 KB Output is correct
3 Correct 479 ms 150876 KB Output is correct
4 Correct 210 ms 79328 KB Output is correct
5 Correct 419 ms 150876 KB Output is correct
6 Correct 145 ms 45156 KB Output is correct
7 Correct 293 ms 150944 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 489 ms 150800 KB Output is correct
2 Correct 26 ms 11624 KB Output is correct
3 Correct 479 ms 150876 KB Output is correct
4 Correct 210 ms 79328 KB Output is correct
5 Correct 419 ms 150876 KB Output is correct
6 Correct 145 ms 45156 KB Output is correct
7 Correct 293 ms 150944 KB Output is correct
8 Incorrect 223 ms 4076 KB Output isn't correct
9 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 489 ms 150800 KB Output is correct
2 Correct 26 ms 11624 KB Output is correct
3 Correct 479 ms 150876 KB Output is correct
4 Correct 210 ms 79328 KB Output is correct
5 Correct 419 ms 150876 KB Output is correct
6 Correct 145 ms 45156 KB Output is correct
7 Correct 293 ms 150944 KB Output is correct
8 Incorrect 223 ms 4076 KB Output isn't correct
9 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1879 ms 155948 KB Output isn't correct
2 Halted 0 ms 0 KB -