oj.uz

Submission #1102697

# Submission time Handle Problem Language Result Execution time Memory
1102697 2024-10-18T16:13:24 Z Requiem Street Lamps (APIO19_street_lamps) C++17
100 / 100
 2210 ms 216248 KB 
#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;
auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
std::mt19937 mt(seed);
int RAND(int l,int r){
    return mt()%(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;
    }


};

typedef TreapNode* Treap;

int getSize(Treap root){
    if (root == NULL) return 0;
    return root->sz;
}

int getSum(Treap root){
    if (root == NULL) return 0;
    return root->sum;

}
void calc(Treap root){
    if (root == NULL) return;
    root->sz = getSize(root->leftChild) + getSize(root->rightChild) + 1;
    root->sum = getSum(root->leftChild) + getSum(root->rightChild) + root->val;
}

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);
    }

    calc(root);
}

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;
    }

    calc(root);
}
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);

    calc(root);
}

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 = getSum(l);
    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:105:11: warning: unused variable 'res' [-Wunused-variable]
  105 |     Treap res, l, r;
      |           ^~~
street_lamps.cpp: In member function 'void BinaryIndexedTree::update(long long int, long long int)':
street_lamps.cpp:197: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]
  197 |         for(int i = id; i < BIT.size(); i += i & (-i)){
      |                         ~~^~~~~~~~~~~~
street_lamps.cpp: At global scope:
street_lamps.cpp:235:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  235 | main()
      | ^~~~
street_lamps.cpp: In function 'bool findKey(Treap, long long int)':
street_lamps.cpp:103:1: warning: control reaches end of non-void function [-Wreturn-type]
  103 | }
      | ^
street_lamps.cpp: In function 'int main()':
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".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:241:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  241 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16976 KB Output is correct
2 Correct 3 ms 16976 KB Output is correct
3 Correct 3 ms 16976 KB Output is correct
4 Correct 4 ms 17072 KB Output is correct
5 Correct 4 ms 16976 KB Output is correct
6 Correct 3 ms 16976 KB Output is correct
7 Correct 4 ms 16976 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 17992 KB Output is correct
2 Correct 166 ms 18328 KB Output is correct
3 Correct 230 ms 21324 KB Output is correct
4 Correct 471 ms 64328 KB Output is correct
5 Correct 570 ms 88648 KB Output is correct
6 Correct 519 ms 66776 KB Output is correct
7 Correct 124 ms 28320 KB Output is correct
8 Correct 1457 ms 216144 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17232 KB Output is correct
2 Correct 3 ms 17232 KB Output is correct
3 Correct 4 ms 17232 KB Output is correct
4 Correct 4 ms 17232 KB Output is correct
5 Correct 532 ms 84292 KB Output is correct
6 Correct 545 ms 85016 KB Output is correct
7 Correct 608 ms 88084 KB Output is correct
8 Correct 2210 ms 216248 KB Output is correct
9 Correct 77 ms 17748 KB Output is correct
10 Correct 72 ms 17736 KB Output is correct
11 Correct 76 ms 17992 KB Output is correct
12 Correct 137 ms 28320 KB Output is correct
13 Correct 2177 ms 216136 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16976 KB Output is correct
2 Correct 3 ms 17188 KB Output is correct
3 Correct 4 ms 16976 KB Output is correct
4 Correct 4 ms 17232 KB Output is correct
5 Correct 301 ms 51612 KB Output is correct
6 Correct 375 ms 58952 KB Output is correct
7 Correct 489 ms 66208 KB Output is correct
8 Correct 582 ms 74904 KB Output is correct
9 Correct 152 ms 17564 KB Output is correct
10 Correct 116 ms 16976 KB Output is correct
11 Correct 166 ms 17564 KB Output is correct
12 Correct 135 ms 16976 KB Output is correct
13 Correct 166 ms 17480 KB Output is correct
14 Correct 141 ms 16976 KB Output is correct
15 Correct 133 ms 28232 KB Output is correct
16 Correct 2098 ms 216220 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16976 KB Output is correct
2 Correct 3 ms 16976 KB Output is correct
3 Correct 3 ms 16976 KB Output is correct
4 Correct 4 ms 17072 KB Output is correct
5 Correct 4 ms 16976 KB Output is correct
6 Correct 3 ms 16976 KB Output is correct
7 Correct 4 ms 16976 KB Output is correct
8 Correct 143 ms 17992 KB Output is correct
9 Correct 166 ms 18328 KB Output is correct
10 Correct 230 ms 21324 KB Output is correct
11 Correct 471 ms 64328 KB Output is correct
12 Correct 570 ms 88648 KB Output is correct
13 Correct 519 ms 66776 KB Output is correct
14 Correct 124 ms 28320 KB Output is correct
15 Correct 1457 ms 216144 KB Output is correct
16 Correct 4 ms 17232 KB Output is correct
17 Correct 3 ms 17232 KB Output is correct
18 Correct 4 ms 17232 KB Output is correct
19 Correct 4 ms 17232 KB Output is correct
20 Correct 532 ms 84292 KB Output is correct
21 Correct 545 ms 85016 KB Output is correct
22 Correct 608 ms 88084 KB Output is correct
23 Correct 2210 ms 216248 KB Output is correct
24 Correct 77 ms 17748 KB Output is correct
25 Correct 72 ms 17736 KB Output is correct
26 Correct 76 ms 17992 KB Output is correct
27 Correct 137 ms 28320 KB Output is correct
28 Correct 2177 ms 216136 KB Output is correct
29 Correct 4 ms 16976 KB Output is correct
30 Correct 3 ms 17188 KB Output is correct
31 Correct 4 ms 16976 KB Output is correct
32 Correct 4 ms 17232 KB Output is correct
33 Correct 301 ms 51612 KB Output is correct
34 Correct 375 ms 58952 KB Output is correct
35 Correct 489 ms 66208 KB Output is correct
36 Correct 582 ms 74904 KB Output is correct
37 Correct 152 ms 17564 KB Output is correct
38 Correct 116 ms 16976 KB Output is correct
39 Correct 166 ms 17564 KB Output is correct
40 Correct 135 ms 16976 KB Output is correct
41 Correct 166 ms 17480 KB Output is correct
42 Correct 141 ms 16976 KB Output is correct
43 Correct 133 ms 28232 KB Output is correct
44 Correct 2098 ms 216220 KB Output is correct
45 Correct 69 ms 17480 KB Output is correct
46 Correct 88 ms 17384 KB Output is correct
47 Correct 241 ms 36052 KB Output is correct
48 Correct 524 ms 63856 KB Output is correct
49 Correct 80 ms 17648 KB Output is correct
50 Correct 71 ms 17560 KB Output is correct
51 Correct 73 ms 17564 KB Output is correct
52 Correct 76 ms 17480 KB Output is correct
53 Correct 74 ms 17480 KB Output is correct
54 Correct 80 ms 17728 KB Output is correct