제출 #39942

#제출 시각아이디문제언어결과실행 시간메모리
39942krauchOGLEDALA (COI15_ogledala)C++14
41 / 100
4000 ms212728 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; typedef pair < ll, int > PLI; #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]; PLI b[N]; set < PLI > st; map < ll, ll > cnt[N]; vector < PLL > vec, vec2; void calc(ll len1, ll len2, ll x) { if (!len1 && !len2) return; calc((len1 - 1) / 2, len2 / 2, x); vec.eb(0, 0); vec2.eb(len1, len2); if (len1 < x) vec.back().F = 0; else if (len1 == x) vec.back().F = 1; else if (len1 & 1) vec.back().F = vec[sz(vec) - 2].F * 2; else vec.back().F = vec[sz(vec) - 2].F + vec[sz(vec) - 2].S; if (len2 < x) vec.back().S = 0; else if (len2 == x) vec.back().S = 1; else if (len2 & 1) vec.back().S = vec[sz(vec) - 2].S * 2; else vec.back().S = vec[sz(vec) - 2].F + vec[sz(vec) - 2].S; return; } int main() { #ifdef krauch freopen("input.txt", "r", stdin); #else //freopen(fname".in", "r", stdin); //freopen(fname".out", "w", stdout); #endif /*calc(40, 40, 1); cout << vec[sz(vec) - 3].F << " " << vec[sz(vec) - 3].S << "\n"; return 0;*/ scanf("%lld%d%d", &L, &n, &m); ll last = 0; forn(i, 1, n) { ll x; scanf("%lld", &x); a[i].F = last + 1; a[i].S = x - 1; if (last < x - 1) { cnt[i][x - last - 1]++; st.insert(PLI(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(PLI(L - last, 0)); } forn(i, 1, m) { scanf("%lld", &b[i].F); b[i].F -= n; b[i].S = i; } int ptr = 1; while (ptr <= m && b[ptr].F <= 0) { ans[b[ptr].S] = a[b[ptr].F + n].S + 1; ++ptr; } ll sum = 0; while (sz(st)) { int i = n + 1 - st.rbegin() -> S; ll len = st.rbegin() -> F; if (!len) break; st.erase(*st.rbegin()); ll val = cnt[i][len]; while (ptr <= m && sum + val >= b[ptr].F) { ll pos = b[ptr].F - sum; ll l = a[i].F, r = a[i].S, lvl = 2; vec.clear(); vec2.clear(); calc(a[i].S - a[i].F + 1, a[i].S - a[i].F + 1, len); while (r - l + 1 > len) { ll mid = (l + r) >> 1ll; ll res = (vec2[sz(vec) - lvl].F == mid - l ? vec[sz(vec) - lvl].F : vec[sz(vec) - lvl].S); if (res >= pos) { r = mid - 1; } else { l = mid + 1; pos -= res; } ++lvl; } if (r - l + 1 != len) assert(0); ans[b[ptr].S] = (l + r) >> 1ll; ++ptr; } if (ptr > m) break; sum += val; if ((len - 1) / 2) { st.insert(PLI((len - 1) / 2, n + 1 - i)); cnt[i][(len - 1) / 2] += val; } if (len / 2) { st.insert(PLI(len / 2, n + 1 - i)); cnt[i][len / 2] += val; } } forn(i, 1, m) { printf("%lld\n", ans[i]); } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

ogledala.cpp: In function 'int main()':
ogledala.cpp:82:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%d%d", &L, &n, &m);
                                  ^
ogledala.cpp:86:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &x);
                          ^
ogledala.cpp:103:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &b[i].F);
                               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...