Submission #1099069

#TimeUsernameProblemLanguageResultExecution timeMemory
1099069Fallout3691Snowball (JOI21_ho_t2)C++17
0 / 100
2 ms600 KiB
#include <bits/stdc++.h> using namespace std; #define int long long signed main() { #ifndef ONLINE_JUDGE freopen("io/input.txt", "r", stdin); freopen("io/output.txt", "w", stdout); freopen("io/error.txt", "w", stderr); #endif int n, q; cin >> n >> q; vector<int> a(n + 2); a[0] = -1e18, a[n + 1] = 1e18; for (int i = 1; i <= n; i++) cin >> a[i]; vector<int> m(q + 1); vector<int> pref(q + 1); map<int, int> mp; mp[0] = 0; for (int i = 1; i <= q; i++) { cin >> m[i]; pref[i] += pref[i - 1] + m[i]; if (mp.find(pref[i]) != mp.end()) continue; if (pref[i] > 0) { auto it = mp.upper_bound(pref[i]); if (it == mp.end()) mp[pref[i]] = i; } else { auto it = mp.lower_bound(pref[i]); if (it == mp.begin()) mp[pref[i]] = i; } } for (int i = 1; i <= n; i++) { int left = a[i], right = a[i]; { int l = a[i - 1], r = a[i]; while (r - l > 1) { int mid = (l + r) / 2; int x = mid - a[i]; int y = mid - a[i - 1]; auto it1 = mp.upper_bound(x); if (it1 == mp.begin()) { l = mid; continue; } --it1; auto it2 = mp.lower_bound(y); if (it2 == mp.end()) { r = mid; continue; } if ((it1 -> second) < (it2 -> second)) r = mid; else l = mid; } auto it1 = mp.upper_bound(r - 1 - a[i]); auto it2 = mp.lower_bound(r - a[i - 1]); if ((it1 != mp.begin()) && ((it2 == mp.end()) ||((--it1) -> second < it2 -> second))) r--; left = r; } { int l = a[i], r = a[i + 1]; int c = 1; while (r - l > 1) { int mid = (l + r) / 2; int x = mid - a[i]; int y = mid - a[i + 1]; auto it1 = mp.lower_bound(x); if (it1 == mp.end()) { r = mid; continue; } auto it2 = mp.upper_bound(y); if (it2 == mp.begin()) { l = mid; continue; } --it2; if ((it1 -> second) < (it2 -> second)) l = mid; else r = mid; } auto it1 = mp.lower_bound(l + 1 - a[i]); auto it2 = mp.upper_bound(l - a[i + 1]); if ((it1 != mp.end()) && ((it2 == mp.begin() || (it1 -> second < (--it2) -> second)))) l++; right = l; } cout << right - left << endl; } return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:75:17: warning: unused variable 'c' [-Wunused-variable]
   75 |             int c = 1;
      |                 ^
Main.cpp:8:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |         freopen("io/input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:9:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |         freopen("io/output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen("io/error.txt", "w", stderr);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...