oj.uz

Submission #1102695

# Submission time Handle Problem Language Result Execution time Memory
1102695 2024-10-18T16:10:46 Z Requiem Street Lamps (APIO19_street_lamps) C++17
100 / 100
 2151 ms 222088 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;

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


};

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: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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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 16980 KB Output is correct
3 Correct 4 ms 16980 KB Output is correct
4 Correct 3 ms 16980 KB Output is correct
5 Correct 3 ms 16980 KB Output is correct
6 Correct 3 ms 17228 KB Output is correct
7 Correct 3 ms 16980 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 17996 KB Output is correct
2 Correct 164 ms 21644 KB Output is correct
3 Correct 212 ms 25420 KB Output is correct
4 Correct 525 ms 69540 KB Output is correct
5 Correct 652 ms 94108 KB Output is correct
6 Correct 582 ms 71756 KB Output is correct
7 Correct 133 ms 34124 KB Output is correct
8 Correct 1563 ms 222028 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 4 ms 17060 KB Output is correct
3 Correct 4 ms 17236 KB Output is correct
4 Correct 6 ms 17236 KB Output is correct
5 Correct 547 ms 88716 KB Output is correct
6 Correct 576 ms 89864 KB Output is correct
7 Correct 600 ms 93260 KB Output is correct
8 Correct 1942 ms 222028 KB Output is correct
9 Correct 63 ms 20556 KB Output is correct
10 Correct 69 ms 20832 KB Output is correct
11 Correct 72 ms 21068 KB Output is correct
12 Correct 116 ms 34124 KB Output is correct
13 Correct 2151 ms 222088 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 4 ms 16980 KB Output is correct
3 Correct 4 ms 17144 KB Output is correct
4 Correct 4 ms 17236 KB Output is correct
5 Correct 320 ms 57492 KB Output is correct
6 Correct 441 ms 64412 KB Output is correct
7 Correct 516 ms 71320 KB Output is correct
8 Correct 656 ms 79228 KB Output is correct
9 Correct 163 ms 21068 KB Output is correct
10 Correct 133 ms 19984 KB Output is correct
11 Correct 162 ms 21068 KB Output is correct
12 Correct 137 ms 20300 KB Output is correct
13 Correct 167 ms 20852 KB Output is correct
14 Correct 136 ms 20044 KB Output is correct
15 Correct 136 ms 34192 KB Output is correct
16 Correct 2081 ms 221968 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 16980 KB Output is correct
3 Correct 4 ms 16980 KB Output is correct
4 Correct 3 ms 16980 KB Output is correct
5 Correct 3 ms 16980 KB Output is correct
6 Correct 3 ms 17228 KB Output is correct
7 Correct 3 ms 16980 KB Output is correct
8 Correct 120 ms 17996 KB Output is correct
9 Correct 164 ms 21644 KB Output is correct
10 Correct 212 ms 25420 KB Output is correct
11 Correct 525 ms 69540 KB Output is correct
12 Correct 652 ms 94108 KB Output is correct
13 Correct 582 ms 71756 KB Output is correct
14 Correct 133 ms 34124 KB Output is correct
15 Correct 1563 ms 222028 KB Output is correct
16 Correct 4 ms 17232 KB Output is correct
17 Correct 4 ms 17060 KB Output is correct
18 Correct 4 ms 17236 KB Output is correct
19 Correct 6 ms 17236 KB Output is correct
20 Correct 547 ms 88716 KB Output is correct
21 Correct 576 ms 89864 KB Output is correct
22 Correct 600 ms 93260 KB Output is correct
23 Correct 1942 ms 222028 KB Output is correct
24 Correct 63 ms 20556 KB Output is correct
25 Correct 69 ms 20832 KB Output is correct
26 Correct 72 ms 21068 KB Output is correct
27 Correct 116 ms 34124 KB Output is correct
28 Correct 2151 ms 222088 KB Output is correct
29 Correct 4 ms 16976 KB Output is correct
30 Correct 4 ms 16980 KB Output is correct
31 Correct 4 ms 17144 KB Output is correct
32 Correct 4 ms 17236 KB Output is correct
33 Correct 320 ms 57492 KB Output is correct
34 Correct 441 ms 64412 KB Output is correct
35 Correct 516 ms 71320 KB Output is correct
36 Correct 656 ms 79228 KB Output is correct
37 Correct 163 ms 21068 KB Output is correct
38 Correct 133 ms 19984 KB Output is correct
39 Correct 162 ms 21068 KB Output is correct
40 Correct 137 ms 20300 KB Output is correct
41 Correct 167 ms 20852 KB Output is correct
42 Correct 136 ms 20044 KB Output is correct
43 Correct 136 ms 34192 KB Output is correct
44 Correct 2081 ms 221968 KB Output is correct
45 Correct 67 ms 19276 KB Output is correct
46 Correct 85 ms 19348 KB Output is correct
47 Correct 235 ms 38980 KB Output is correct
48 Correct 452 ms 69004 KB Output is correct
49 Correct 75 ms 21068 KB Output is correct
50 Correct 73 ms 21068 KB Output is correct
51 Correct 79 ms 21324 KB Output is correct
52 Correct 81 ms 21584 KB Output is correct
53 Correct 77 ms 21632 KB Output is correct
54 Correct 89 ms 21580 KB Output is correct