// REPUTATION RATING =
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()
using namespace std;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 3e5 + 5;
//const int oo = 1e9;
const int mod = 1e9 + 7;
int n, q, a[N], L[N], R[N], X[N];
string s, T[N];
namespace sub1{
int m[105][105];
void solve(){
for(int i = 1; i <= n; i ++) m[1][i] = a[i];
for(int t = 1; t <= q; t ++){
string type; cin >> type;
if(type[0] == 't'){
int x; cin >> x;
a[x] = 1 - a[x];
}else{
int l, r, ans = 0; cin >> l >> r;
for(int j = 1; j <= t; j ++){
bool ff = true;
for(int i = l; i < r; i ++) if(m[j][i] == 0){
ff = false;
break;
}
ans += ff;
}
cout << ans << "\n";
}
for(int i = 1;i <= n; i ++) m[t + 1][i] = a[i];
}
}
}
namespace sub5{
int op[N];
int time[N], kq[N];
struct Q{
int l,r,w;
} query[N];
vector<int> node[N], BIT[N];
void fakeupdate(int x,int y){
for(; x <= n; x += x & -x) node[x].pb(y);
}
void fakeGet(int x,int y){
for(; x > 0; x -= x & -x) node[x].pb(y);
}
void FGet(int x,int y,int i,int j){
fakeGet(x - 1, y - 1);
fakeGet(x - 1, j);
fakeGet(i, y - 1);
fakeGet(i, j);
}
void update(int x,int yy,int val){
for(; x <= n; x += x & -x)
for(int y = lower_bound(all(node[x]), yy) - node[x].begin() + 1; y <= n; y += y & -y){
BIT[x][y - 1] += val;
}
}
int get(int x,int yy){
int ret = 0;
for(; x > 0; x -= x & -x){
for(int y = lower_bound(all(node[x]), yy) - node[x].begin() + 1; y > 0; y -= y & -y){
ret += BIT[x][y - 1];
}
}
return ret;
}
int GET(int x,int y,int i,int j){
return get(i, j) - get(x - 1, j) - get(i, y - 1) + get(x - 1, y - 1);
}
void solve(){
set<int> s;
s.insert(0);
s.insert(n + 1);
time[0] = 1;
time[n + 1] = 1;
for(int i = 1; i <= n; i ++){
op[i] = a[i];
if(!a[i]){
s.insert(i);
time[i] = 1;
}
}
for(int i = 1;i <= q; i ++){
string type = T[i];
if(type[0] == 't'){
int x = X[i];
if(op[x]){
auto j = s.lower_bound(x);
int ri = (*j);
j--;
int le = (*j);
query[i] = {le + 1, ri - 1, i - time[le] + 1};
fakeupdate(le + 1, ri - 1);
time[le] = i + 1;
time[x] = i + 1;
s.insert(x);
}else{
auto j = s.lower_bound(x);
int ri = (*j);
j--;
int le = (*j);
query[i] = {le + 1, ri - 1, i - time[le] + 1};
fakeupdate(le + 1, ri - 1);
time[le] = i + 1;
s.erase(x);
}
op[x] = 1 - op[x];
// for(auto j : s) cout << j << " ";
// cout << "\n";
}else{
int l = L[i], r = R[i];
auto j = s.lower_bound(l);
cerr << i << " " << l << " " << r << " " << (*j) << "r\n";
if((*j) > r){
if((*j) > l) j--;
cerr << (*j) << " " << time[(*j)] << "g\n";
kq[i] = i - time[(*j)] + 1;
}
FGet(1, r, l, n);
}
// for(auto j : s) cout << j << " ";
// cout << time[0] << "\n";
}
for(int i = 1; i <= n; i ++){
sort(all(node[i]));
node[i].resize(unique(all(node[i])) - node[i].begin());
for(auto j : node[i]) BIT[i].pb(0);
}
for(int i = 1;i <= q; i ++){
string type = T[i];
if(type[0] == 't'){
int x = X[i];
int l = query[i].l, r = query[i].r, w = query[i].w;
update(l, r, w);
}else{
int l = L[i], r = R[i];
cout << GET(1, r, l, n) + kq[i] << "\n";
}
cerr << i << "f\n";
}
cerr << "d\n";
exit(0);
}
}
#define LOCAL
#ifdef LOCAL
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define task "v"
if(fopen(task ".inp","r")){
freopen(task ".inp","r",stdin);
freopen(task ".out","w",stdout);
}
cin >> n >> q >> s;
for(int i = 1; i <= n; i ++) a[i] = s[i - 1] - '0';
// if(n <= 100 && q <= 100){
// sub1 :: solve();
// }
for(int i = 1; i <= q; i ++) {
cin >> T[i];
if(T[i][0] == 't') cin >> X[i];
else{
cin >> L[i] >> R[i];
R[i]--;
}
}
sub5 :: solve();
}
#endif // LOCAL
Compilation message
street_lamps.cpp: In function 'void sub5::solve()':
street_lamps.cpp:152:22: warning: unused variable 'j' [-Wunused-variable]
152 | for(auto j : node[i]) BIT[i].pb(0);
| ^
street_lamps.cpp:158:21: warning: unused variable 'x' [-Wunused-variable]
158 | int x = X[i];
| ^
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:180:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
180 | freopen(task ".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:181:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
181 | freopen(task ".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
39512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2662 ms |
134884 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
47 ms |
76012 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
52 ms |
80432 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
39512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
