This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 3e5+5;
vector<int> seg(MAXN * 2, 1e9);
int n, q;
void upd(int v, int val)
{
for(seg[v += n] = val; v > 1; v >>= 1)
{
seg[v >> 1] = max(seg[v],seg[v ^ 1]);
}
}
int get(int l, int r)
{
int val = 0;
for(l += n, r += n + 1; l < r; l >>= 1, r >>= 1)
{
if(l & 1)
val = max(val, seg[l++]);
if(r & 1)
val = max(val, seg[--r]);
}
return val;
}
vector< pair<string, pair<int, int> > > queries(MAXN);
string stats[MAXN];
int main()
{
cin >> n >> q;
string in;
cin >> in;
in = " " + in;
stats[0] = in;
int maxdiff = 0;
int ltog = 0, fque = 1e9;
for(int i = 1; i <= q; i++)
{
cin >> queries[i].first;
if(queries[i].first == "toggle")
{
cin >> queries[i].second.first;
ltog = i;
} else {
cin >> queries[i].second.first >> queries[i].second.second;
maxdiff = max(maxdiff, queries[i].second.second - queries[i].second.first);
fque = min(fque, i);
}
}
if(max(n, q) <= 100) // Subtask 1
{
for(int i = 1; i <= q; i++)
{
if(queries[i].first == "toggle")
{
in[queries[i].second.first] = (in[queries[i].second.first] == '1' ? '0' : '1');
stats[i] = in;
} else
{
stats[i] = in;
int pos = 0;
for(int ava = 0; ava < i; ava++) {
string temp = stats[ava];
int beg = queries[i].second.first;
int end = queries[i].second.second;
while(beg < end)
{
if(temp[beg] == '1')
beg++;
else
break;
}
if(beg == end)
pos++;
}
cout << pos << "\n";
}
}
} else
{
if(maxdiff == 1) // Subtask 2
{
vector<int> roads(n+5, 0);
vector<int> last(n+5, 0);
for(int i = 1; i <= q; i++)
{
int idx = queries[i].second.first;
if(queries[i].first == "toggle")
{
if(in[idx] == '1')
{
roads[idx] += i - last[idx];
in[idx] = '0';
} else
{
last[idx] = i;
in[idx] = '1';
}
} else
{
int val = roads[idx];
if(in[idx] == '1')
{
val += i - last[idx];
}
cout << val << "\n";
}
}
} else //Subtask 3
{
for(int i = 1; i <= n; i++)
{
if(in[i] == '1') {
upd(i, 1);
}
}
for(int i = 1; i <= q; i++)
{
if(queries[i].first == "toggle")
{
upd(queries[i].second.first, i + 1);
} else
{
int fi = get(queries[i].second.first, queries[i].second.second - 1);
if(fi == 1e9)
cout << "0\n";
else
cout << i - fi + 1 << "\n";
}
}
}
}
}
Compilation message (stderr)
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:37:9: warning: variable 'ltog' set but not used [-Wunused-but-set-variable]
37 | int ltog = 0, fque = 1e9;
| ^~~~
# | 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... |