#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "streetlamp"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
const int MAXN = 3e5 + 9;
int RAND(int l, int r){
return rand() % (r - l + 1) + l;
}
struct TreapNode{
int key = 0, val = 0, pr = 0, sz = 0, sum = 0;
TreapNode *leftChild, *rightChild;
TreapNode(int _key = 0, int _val = 0){
key = _key;
val = _val;
sum = _val;
pr = RAND(1, 3e5);
sz = 1;
leftChild = rightChild = NULL;
}
int getSize(){
if (this == NULL) return 0;
return this->sz;
}
int getSum(){
if (this == NULL) return 0;
return this->sum;
}
void calc(){
if (this == NULL) return;
this->sz = leftChild->getSize() + rightChild->getSize() + 1;
this->sum = leftChild->getSum() + rightChild->getSum() + val;
}
};
typedef TreapNode* Treap;
void Split(Treap root, Treap &l, Treap &r, int key){
if (root == NULL){
l = r = NULL;
return;
}
if (root->key <= key){
l = root;
Split(root->rightChild, l->rightChild, r, key);
}
else{
r = root;
Split(root->leftChild, l, r->leftChild, key);
}
root->calc();
}
void Merge(Treap &root, Treap l, Treap r){
if (!l or !r) {
root = (!l) ? r : l;
return;
}
if (l->pr < r->pr) {
Merge(l->rightChild, l->rightChild, r);
root = l;
}
else {
Merge(r->leftChild, l, r->leftChild);
root = r;
}
root->calc();
}
bool findKey(Treap root, int key){
if (root == NULL) return false;
if (root->key == key) return true;
if (root->key > key) return findKey(root->leftChild, key);
if (root->key < key) return findKey(root->rightChild, key);
}
void insertKey(Treap &root, int key, int val){
Treap res, l, r;
Split(root, l, r, key - 1);
Merge(l, l, new TreapNode(key, val));
Merge(l, l, r);
root = l;
}
void updateKey(Treap &root, int key, int value){
if (root->key == key) root->val += value;
if (root->key < key) updateKey(root->rightChild, key, value);
if (root->key > key) updateKey(root->leftChild, key, value);
root->calc();
}
void goUpdateKey(Treap &root, int key, int value){
if (!findKey(root, key)){
insertKey(root, key, value);
return;
}
updateKey(root, key, value);
}
int get(Treap &root, int key){
Treap l, r;
Split(root, l, r, key);
int res = l->getSum();
Merge(l, l, r);
root = l;
return res;
}
void go(Treap root){
if (root == NULL) return;
go(root->leftChild);
cerr << root->val << ' ' ;
go(root->rightChild);
}
Treap segtree[MAXN << 2];
void update(int nn, int l, int r, int L, int R, int B, int T, int val){
if (l >= L and r <= R){
goUpdateKey(segtree[nn], B, val);
goUpdateKey(segtree[nn], T + 1, -val);
return;
}
if (l > R or r < L) return;
int mid = (l + r) >> 1;
update(nn << 1, l, mid, L, R, B, T, val);
update(nn << 1 | 1, mid + 1, r, L, R, B, T, val);
}
void getPoint(int nn, int l, int r, int x1, int y1, int &res){
res +=get(segtree[nn], y1);
if (l == r) return;
int mid = (l + r) >> 1;
if (x1 <= mid) getPoint(nn << 1, l, mid, x1, y1, res);
else getPoint(nn << 1 | 1, mid + 1, r, x1, y1, res);
}
Treap root;
char lamp[MAXN];
struct Query{
string type;
int u, l, r;
} Query[MAXN];
struct BinaryIndexedTree{
vector<int> BIT;
BinaryIndexedTree(int sz = 0){
BIT.resize(sz + 9, 0);
}
int get(int id){
int res = 0;
for(int i = id; i > 0; i -= i & (-i)){
res += BIT[i];
}
return res;
}
void update(int id, int val){
for(int i = id; i < BIT.size(); i += i & (-i)){
BIT[i] += val;
}
}
int getRange(int l, int r){
return get(r) - get(l - 1);
}
int furthestLeft(int x){
int l = 1, r = x, res = -1;
while(l <= r){
int mid = (l + r) >> 1;
if (getRange(mid, x) == x - mid + 1){
res = mid;
r = mid - 1;
}
else l = mid + 1;
}
return res;
}
int furthestRight(int x){
int l = x, r = BIT.size() - 1, res = -1;
while(l <= r){
int mid = (l + r) >> 1;
if (getRange(x, mid) == mid - x + 1){
res = mid;
l = mid + 1;
}
else r = mid - 1;
}
return res;
}
//get(l - 1) + l + 1 == get(r) - r. Tìm vị trí 1 đầu tiên thỏa.
};
int n, q;
main()
{
fast;
srand(time(NULL));
if (fopen(TASKNAME".inp","r")){
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".out","w",stdout);
}
cin >> n >> q;
FOR(i, 1, n){
cin >> lamp[i];
}
FOR(i, 1, q){
cin >> Query[i].type;
if (Query[i].type == "toggle") cin >> Query[i].u;
else cin >> Query[i].l >> Query[i].r;
}
BinaryIndexedTree BIT(n);
FOR(i, 1, n){
if (lamp[i] == '1') {
BIT.update(i, 1);
int l = BIT.furthestLeft(i);
// cout << l << ' ' << i << endl;
update(1, 1, n, l, i, i, i, -1);
}
}
FOR(i, 1, q){
if (Query[i].type == "toggle"){
int u = Query[i].u;
if (lamp[u] == '0'){
lamp[u] = '1';
BIT.update(u, 1);
int L = BIT.furthestLeft(u);
int R = BIT.furthestRight(u);
// cout<< L << ' ' << u << ' ' << u << ' '<< R << ' ' << -(i + 1) << endl;
update(1, 1, n, L, u, u, R, -(i + 1));
int res = 0;
getPoint(1, 1, n, 1, 5, res);
// cout << res << endl;
}
else{
lamp[u] = '0';
int L = BIT.furthestLeft(u);
int R = BIT.furthestRight(u);
update(1, 1, n, L, u, u, R, +i + 1);
BIT.update(u, -1);
}
}
else{
int l = Query[i].l;
int r = Query[i].r - 1;
int res = 0;
getPoint(1, 1, n, l, r, res);
if (lamp[l] == '1' and lamp[r] == '1' and BIT.furthestRight(l) >= r){
res += i + 1;
}
cout << res << endl;
}
}
}
/**
Warning:
Đọc sai đề???
Cận lmao
Code imple thiếu case nào không.
Limit.
**/
Compilation message
street_lamps.cpp: In function 'void insertKey(TreapNode*&, long long int, long long int)':
street_lamps.cpp:104:11: warning: unused variable 'res' [-Wunused-variable]
104 | Treap res, l, r;
| ^~~
street_lamps.cpp: In member function 'void BinaryIndexedTree::update(long long int, long long int)':
street_lamps.cpp:196:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
196 | for(int i = id; i < BIT.size(); i += i & (-i)){
| ~~^~~~~~~~~~~~
street_lamps.cpp: At global scope:
street_lamps.cpp:234:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
234 | main()
| ^~~~
street_lamps.cpp: In function 'bool findKey(Treap, long long int)':
street_lamps.cpp:102:1: warning: control reaches end of non-void function [-Wreturn-type]
102 | }
| ^
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:239:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
239 | freopen(TASKNAME".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:240:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
240 | freopen(TASKNAME".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp: In member function 'long long int TreapNode::getSize()':
street_lamps.cpp:40:9: warning: 'nonnull' argument 'this' compared to NULL [-Wnonnull-compare]
40 | if (this == NULL) return 0;
| ^~
street_lamps.cpp: In member function 'long long int TreapNode::getSum()':
street_lamps.cpp:45:9: warning: 'nonnull' argument 'this' compared to NULL [-Wnonnull-compare]
45 | if (this == NULL) return 0;
| ^~
street_lamps.cpp: In member function 'void TreapNode::calc()':
street_lamps.cpp:50:9: warning: 'nonnull' argument 'this' compared to NULL [-Wnonnull-compare]
50 | if (this == NULL) return;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
26 ms |
34260 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
60 ms |
37260 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
25 ms |
34132 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
32 ms |
34216 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
26 ms |
34260 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
