Submission #1025405

#TimeUsernameProblemLanguageResultExecution timeMemory
1025405ThanhsIndex (COCI21_index)C++14
110 / 110
534 ms32884 KiB
#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; #define int long long // #define double long double #define pb push_back #define endl '\n' #define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #define setmin(x, y) x = min((x), (y)) #define setmax(x, y) x = max((x), (y)) #define sqr(x) ((x) * (x)) #define fi first #define se second mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count()); int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);} const int N = 2e5 + 5; const int mod = 1e9 + 7; const int p = 31; struct Query { int l, r, lx, rx, m, cur; }Q[N]; int n, q, a[N], bit[N]; vector<pair<int, int>> ops[N]; void upd(int i) { for (; i <= 2e5; i+= i & -i) bit[i]++; } int get(int i) { int res = 0; for (; i; i -= i & -i) res += bit[i]; return res; } signed main() { if (fopen("in.txt", "r")) { freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); } fastIO cin >> n >> q; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= q; i++) { cin >> Q[i].l >> Q[i].r; Q[i].lx = 1, Q[i].rx = Q[i].r - Q[i].l + 2; } while (1) { bool changed = 0; for (int i = 1; i <= q; i++) if (Q[i].lx < Q[i].rx - 1) { Q[i].m = Q[i].lx + Q[i].rx >> 1; Q[i].cur = 0; ops[Q[i].l - 1].push_back({i, -1}); ops[Q[i].r].push_back({i, 1}); } memset(bit, 0, sizeof bit); ops[0].clear(); for (int i = 1; i <= n; i++) { upd(a[i]); for (auto p : ops[i]) Q[p.fi].cur += p.se * (get(2e5) - get(Q[p.fi].m - 1)); ops[i].clear(); } for (int i = 1; i <= q; i++) if (Q[i].lx < Q[i].rx - 1) { if (Q[i].cur >= Q[i].m) Q[i].lx = Q[i].m; else Q[i].rx = Q[i].m; changed = true; } if (!changed) break; } for (int i = 1; i <= q; i++) cout << Q[i].lx << endl; }

Compilation message (stderr)

index.cpp: In function 'int main()':
index.cpp:67:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |                 Q[i].m = Q[i].lx + Q[i].rx >> 1;
      |                          ~~~~~~~~^~~~~~~~~
index.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         freopen("in.txt","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
index.cpp:50:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         freopen("out.txt","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...