Submission #563445

#TimeUsernameProblemLanguageResultExecution timeMemory
563445Tien_NoobStreet Lamps (APIO19_street_lamps)C++17
0 / 100
154 ms122984 KiB
//Make CSP great again //Vengeance #include <bits/stdc++.h> #define TASK "TESTCODE" #define Log2(x) 31 - __builtin_clz(x) using namespace std; const int N = 3e5; set<pair<int, int> > pivot, dp[N + 1]; set<int> query[N + 1]; map<int, int> res[N + 1]; int n, q, t[N + 1], a[N + 1], b[N + 1]; string s; set<pair<int, int> > :: iterator Range(int x) { auto it = pivot.upper_bound({x, N + 10}); --it; return it; } void read() { cin >> n >> q >> s; s = '?' + s; for (int i = 1; i <= q; ++ i) { string r; cin >> r; if (r == "query") { t[i] = 1; cin >> a[i] >> b[i]; query[a[i]].insert(b[i]); } else { t[i] = 0; cin >> a[i]; } } for (int i = 1; i <= n + 1; ++ i) { pivot.insert({i, i}); if (!query[i].empty()) { dp[i].insert({*query[i].begin(), i}); } } for (int i = 1; i <= n; ++ i) { if (s[i] == '1') { pair<int, int> tmp = *Range(i); pivot.erase(tmp); pivot.erase({i + 1, i + 1}); pivot.insert({tmp.first, i + 1}); swap(dp[i], dp[i + 1]); for (auto &p : dp[i]) { dp[i + 1].insert(p); } dp[i].clear(); } } for (int i = 1; i <= n + 1; ++ i) { while(!dp[i].empty() && dp[i].begin()->first <= i) { int u = dp[i].begin()->second; res[u][dp[i].begin()->first] = 0; query[u].erase(query[u].begin()); dp[i].erase(dp[i].begin()); if (!query[u].empty()) { dp[i].insert({*query[u].begin(), u}); } } } } void solve() { for (int i = 1; i <= q; ++ i) { if (t[i] == 0) { if (s[a[i]] == '1') { auto it = Range(a[i]); int l = it->first, r = it->second; pivot.erase(it); pivot.insert({l, a[i]}); pivot.insert({a[i] + 1, r}); s[a[i]] = '0'; } else { auto it1 = Range(a[i]), it2 = Range(a[i] + 1); int l = it1->first, r = it2->second; if (dp[a[i]].size() > dp[r].size()) { swap(dp[a[i]], dp[r]); } for (auto &p : dp[a[i]]) { dp[r].insert(p); } dp[a[i]].clear(); while(!dp[r].empty() && dp[r].begin()->first <= r) { int u = dp[r].begin()->second; res[u][dp[r].begin()->first] = i; query[u].erase(query[u].begin()); dp[r].erase(dp[r].begin()); if (!query[u].empty()) { dp[r].insert({*query[u].begin(), u}); } } pivot.erase(it1); pivot.erase(it2); pivot.insert({l, r}); s[a[i]] = '1'; } } else { if (res[a[i]].find(b[i]) == res[a[i]].end()) { cout << 0 << '\n'; } else { cout << i - res[a[i]][b[i]] << '\n'; } } } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); if (fopen(TASK".INP", "r")) { freopen(TASK".INP", "r", stdin); //freopen(TASK".OUT", "w", stdout); } int t = 1; bool typetest = false; if (typetest) { cin >> t; } for (int __ = 1; __ <= t; ++ __) { //cout << "Case " << __ << ": "; read(); solve(); } }

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:142:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...