oj.uz

Submission #377579

# Submission time Handle Problem Language Result Execution time Memory
377579 2021-03-14T10:28:07 Z kartel Specijacija (COCI20_specijacija) C++14
20 / 110
 4000 ms 4076 KB 
#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
//#include <time.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
//#define M ll(1e9 + 7)
#define M ll(998244353)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <int, int>
#define all(x) (x).begin(), (x).end()
#define arr_all(x, n) (x + 1), (x + 1 + n)
#define vi vector<int>
#define eps (ld)1e-9
using namespace std;
typedef long long ll;
//using namespace __gnu_pbds;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef double ld;
typedef unsigned long long ull;
typedef short int si;

const int N = (1000 + 1) * (1000 + 2) + 50;

const int MAXN = 2e5 + 50;

int n, q, t;
ll a[MAXN];

ll get(ll lvl, ll pos) {return (lvl * (lvl - 1)) / 2ll + 1 + pos;}

ll geth(ll x) {
    ll l = 1;
    ll r = n + 1;

    while (l < r) {
        ll md = (l + r + 1) / 2ll;

        if (md * (md - 1) / 2ll < x) {
            l = md;
        }
        else {
            r = md - 1;
        }
    }

    return r;
}

ll getpr(ll v, ll h) {
    ll nm = v - (h * (h - 1) / 2ll + 1);

    if (nm == h - 1) {
        return get(h - 1, nm - 1);
    }

    if (nm) {
        ll pr1 = get(h - 1, nm - 1);
        ll pr2 = get(h - 1, nm);

        if (a[h - 1] == pr1) {
            return pr1;
        }
        else if (a[h - 1] == pr2) {
            return pr2;
        }
        else {
            if (a[h - 1] < pr1) {
                return pr1;
            }
            else {
                return pr2;
            }
        }
    }
    else {
        return get(h - 1, nm);
    }
}

int main()
{
//    mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());;
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	in("toys.in");
//	out("toys.out");
//    in("input.txt");
//    out("output.txt");
//    cerr.precision(9); cerr << fixed;

//    clock_t tStart = clock();

    cin >> n >> q >> t;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
//        a[i] = get(i, 0);
    }

    while (q--) {
        ll x, y;
        cin >> x >> y;

        ll hx = geth(x);
        ll hy = geth(y);

        while (hx < hy) {
            y = getpr(y, hy--);
        }

        while (hx > hy) {
            x = getpr(x, hx--);
        }


        while (x != y) {
            x = getpr(x, hx--);
            y = getpr(y, hy--);
        }

        cout << x << el;
    }
}

/*
19999900000
20000100000
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2924 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Correct 30 ms 4076 KB Output is correct
4 Correct 22 ms 2284 KB Output is correct
5 Correct 28 ms 3564 KB Output is correct
6 Correct 9 ms 1516 KB Output is correct
7 Correct 42 ms 3436 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2924 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Correct 30 ms 4076 KB Output is correct
4 Correct 22 ms 2284 KB Output is correct
5 Correct 28 ms 3564 KB Output is correct
6 Correct 9 ms 1516 KB Output is correct
7 Correct 42 ms 3436 KB Output is correct
8 Correct 1819 ms 2592 KB Output is correct
9 Correct 869 ms 2792 KB Output is correct
10 Correct 1795 ms 3020 KB Output is correct
11 Correct 222 ms 2668 KB Output is correct
12 Correct 1787 ms 2668 KB Output is correct
13 Correct 411 ms 2412 KB Output is correct
14 Correct 860 ms 3056 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2924 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Correct 30 ms 4076 KB Output is correct
4 Correct 22 ms 2284 KB Output is correct
5 Correct 28 ms 3564 KB Output is correct
6 Correct 9 ms 1516 KB Output is correct
7 Correct 42 ms 3436 KB Output is correct
8 Correct 1819 ms 2592 KB Output is correct
9 Correct 869 ms 2792 KB Output is correct
10 Correct 1795 ms 3020 KB Output is correct
11 Correct 222 ms 2668 KB Output is correct
12 Correct 1787 ms 2668 KB Output is correct
13 Correct 411 ms 2412 KB Output is correct
14 Correct 860 ms 3056 KB Output is correct
15 Execution timed out 4058 ms 2004 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 4059 ms 2028 KB Time limit exceeded
2 Halted 0 ms 0 KB -