Submission #39915

#TimeUsernameProblemLanguageResultExecution timeMemory
39915krauchOGLEDALA (COI15_ogledala)C++14
0 / 100
4000 ms31756 KiB
/* _ _ _______ _ _ | | / / | _____| | | / / | | / / | | | | / / | |/ / | |_____ | |/ / | |\ \ | _____| | |\ \ | | \ \ | | | | \ \ | | \ \ | |_____ | | \ \ |_| \_\ |_______| |_| \_\ */ #include <bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef long long ll; typedef double ld; typedef pair <int, int> PII; typedef pair <ll, ll> PLL; #define F first #define S second #define pb push_back #define eb emplace_back #define right(x) x << 1 | 1 #define left(x) x << 1 #define forn(x, a, b) for (int x = a; x <= b; ++x) #define for1(x, a, b) for (int x = a; x >= b; --x) #define mkp make_pair #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() #define y1 kekekek #define fname "" const ll ool = 1e18 + 9; const int oo = 1e9 + 9, base = 1e9 + 7; const ld eps = 1e-7; const int N = 2e5 + 6; int n, m; ll L, ans[N]; PLL a[N], b[N]; map < PLL, ll > d; map < ll, ll > cnt[N]; set < PLL > st; ll get(ll len, ll x) { if (d.count(PLL(len, x))) return d[PLL(len, x)]; if (len == x) return d[PLL(len, x)] = 1; if (len < x) return d[PLL(len, x)] = 0; return d[PLL(len, x)] = get((len - 1) / 2, x) + get(len / 2, x); } int main() { #ifdef krauch freopen("input.txt", "r", stdin); #else //freopen(fname".in", "r", stdin); //freopen(fname".out", "w", stdout); #endif scanf("%I64d%d%d", &L, &n, &m); ll last = 0; forn(i, 1, n) { ll x; scanf("%I64d", &x); a[i].F = last + 1; a[i].S = x - 1; if (last < x - 1) { cnt[i][x - last - 1]++; st.insert(mkp(x - last - 1, n + 1 - i)); } last = x; } a[n + 1].F = last + 1; a[n + 1].S = L; if (last != L) { cnt[n + 1][L - last]++; st.insert(mkp(L - last, 0)); } forn(i, 1, m) { scanf("%I64d", &b[i].F); b[i].F -= n; b[i].S = i; } sort(b + 1, b + m + 1); int ptr = 1; ll sum = 0; while (sz(st)) { int i = n + 1 - st.rbegin() -> S; ll len = st.rbegin() -> F; st.erase(*st.rbegin()); ll val = cnt[i][len]; while (ptr <= m && sum + val >= b[ptr].F) { if (b[ptr].F <= 0) { ans[b[ptr].S] = a[b[ptr].F + n].S + 1; ++ptr; continue; } ll pos = b[ptr].F - sum; ll l = a[i].F, r = a[i].S; while (r - l + 1 != len) { ll mid = (l + r) >> 1ll; if (get(mid - l, len) >= pos) { r = mid - 1; } else { l = mid + 1; pos -= get(mid - l, len); } } ans[b[ptr].S] = (l + r) >> 1ll; ++ptr; } if (ptr > m) break; sum += val; st.insert(mkp((len - 1) / 2, n + 1 - i)); cnt[i][(len - 1) / 2] += val; st.insert(mkp(len / 2, n + 1 - i)); cnt[i][len / 2] += val; } forn(i, 1, m) { printf("%I64d\n", ans[i]); } return 0; }

Compilation message (stderr)

ogledala.cpp: In function 'int main()':
ogledala.cpp:65:34: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll* {aka long long int*}' [-Wformat=]
     scanf("%I64d%d%d", &L, &n, &m);
                                  ^
ogledala.cpp:69:26: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll* {aka long long int*}' [-Wformat=]
         scanf("%I64d", &x);
                          ^
ogledala.cpp:86:31: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
         scanf("%I64d", &b[i].F);
                               ^
ogledala.cpp:130:33: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll {aka long long int}' [-Wformat=]
         printf("%I64d\n", ans[i]);
                                 ^
ogledala.cpp:65:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%I64d%d%d", &L, &n, &m);
                                   ^
ogledala.cpp:69:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%I64d", &x);
                           ^
ogledala.cpp:86:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%I64d", &b[i].F);
                                ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...