Submission #377568

#TimeUsernameProblemLanguageResultExecution timeMemory
377568kartelSpecijacija (COCI20_specijacija)C++14
0 / 110
4136 ms830104 KiB
#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; map <ll, int> mp; 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) { ll pr1 = get(h - 1, nm - 1); ll pr2 = get(h - 1, nm); if (mp[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++) { ll a; cin >> a; mp[a] = 1; } 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; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...