이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//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 + 1});
--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(i);
int l = it->first, r = it->second;
pivot.erase(it);
pivot.insert({l, i});
pivot.insert({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();
}
}
컴파일 시 표준 에러 (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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |