oj.uz

Submission #257740

# Submission time Handle Problem Language Result Execution time Memory
257740 2020-08-04T16:55:01 Z 2qbingxuan Street Lamps (APIO19_street_lamps) C++14
100 / 100
 2201 ms 365964 KB 
#include <bits/stdc++.h>
#ifdef local
#define debug(...) qqbx(#__VA_ARGS__, __VA_ARGS__)
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
template<typename H, typename ...T>
void qqbx(const char *s, const H h, T ...args) {
    for(; *s && *s != ','; ++s) if(*s != ' ') std::cerr << *s;
    std::cerr << " = " << h << (sizeof...(T) ? ", " : "\n");
    if constexpr(sizeof...(T)) qqbx(++s, args...);
}
#else
#define debug(...) ((void)0)
#define safe ((void)0)
#endif // local
#define pb emplace_back

using namespace std;
typedef int64_t ll;
const int N = 300025;
const int inf = 1e9;

int n, q;
bool light[N];
map<pair<int,int>,int> last;
/* vector<tuple<int,int,int>> sg; */
struct Segtree {
    struct node {
        node *l, *r;
        int sum;
        node(int s) : sum(s), l(nullptr), r(nullptr) {}
        void pull() {
            sum = 0;
            if(l) sum += l->sum;
            if(r) sum += r->sum;
        }
    } *root = nullptr;
    void add(int p, int d, int l, int r, node *&now) {
        if(!now) now = new node(0);
        if(l+1 == r) return now->sum += d, void();
        int m = l+(r-l)/2;
        if(p < m)
            add(p, d, l, m, now->l);
        else
            add(p, d, m, r, now->r);
        now->pull();
    }
    int query(int ql, int qr, int l, int r, node *now) {
        if(!now || l >= qr || r <= ql) return 0;
        if(ql <= l && r <= qr) return now->sum;
        int m = l+(r-l)/2;
        return query(ql, qr, l, m, now->l) + query(ql, qr, m, r, now->r);
    }
} sgt[N];
void add(int L, int R, int D) {
    /* sg.pb(L, R, d); */
    for(int i = L+1; i < N; i += i&-i) sgt[i].add(R, D, 0, N, sgt[i].root);
}
void toggle(int x, int now) {
    auto &mp = last;
    light[x] = !light[x];
    if(light[x]) {
        int l = x, r = x;
        if(x-1 >= 0 && light[x-1]) {
            auto it = prev(mp.lower_bound({x, 0}));
            auto [L, R] = it->first;
            add(L, R, now - it->second);
            l = L;
            mp.erase(it);
        }
        if(x+1 < n && light[x+1]) {
            auto it = mp.upper_bound({x, inf});
            auto [L, R] = it->first;
            add(L, R, now - it->second);
            r = R;
            mp.erase(it);
        }
        mp[{l, r}] = now;
    } else {
        auto it = prev(mp.upper_bound({x, inf}));
        auto [L, R] = it->first;
        add(L, R, now - it->second);
        mp.erase(it);
        if(L <= x-1) mp[{L, x-1}] = now;
        if(R >= x+1) mp[{x+1, R}] = now;
    }
}
int query(int a, int b, int now) {
    --b;
    int ans = 0;
    {
        if(light[a]) {
            auto it = prev(last.upper_bound({a, inf}));
            auto [l, r] = it->first;
            if(l <= a && b <= r) ans += now - it->second;
        }
    }
    for(int i = a+1; i > 0; i -= i&-i)
        ans += sgt[i].query(b, N, 0, N, sgt[i].root);
    /* for(auto [l, r, d]: sg) { */
    /*     if(l <= a && b <= r) */
    /*         ans += d; */
    /* } */
    return ans;
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    string s;
    cin >> n >> q >> s;
    for(int i = 0; i < n; i++) if(s[i] == '1') toggle(i, 0);
    for(int now = 1; now <= q; now++) {
        char com[7];
        cin >> com;
        if(com[0] == 'q') {
            int a, b;
            cin >> a >> b;
            --a, --b;
            cout << query(a, b, now) << '\n';
        } else if(com[0] == 't') {
            int x;
            cin >> x;
            --x;
            toggle(x, now);
        }
    }
}

Compilation message

street_lamps.cpp: In constructor 'Segtree::node::node(int)':
street_lamps.cpp:29:13: warning: 'Segtree::node::sum' will be initialized after [-Wreorder]
         int sum;
             ^~~
street_lamps.cpp:28:15: warning:   'Segtree::node* Segtree::node::l' [-Wreorder]
         node *l, *r;
               ^
street_lamps.cpp:30:9: warning:   when initialized here [-Wreorder]
         node(int s) : sum(s), l(nullptr), r(nullptr) {}
         ^~~~
street_lamps.cpp: In function 'void toggle(int, int)':
street_lamps.cpp:65:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
             auto [L, R] = it->first;
                  ^
street_lamps.cpp:72:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
             auto [L, R] = it->first;
                  ^
street_lamps.cpp:80:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         auto [L, R] = it->first;
              ^
street_lamps.cpp: In function 'int query(int, int, int)':
street_lamps.cpp:93:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
             auto [l, r] = it->first;
                  ^

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 1656 KB Output is correct
2 Correct 494 ms 5588 KB Output is correct
3 Correct 759 ms 14200 KB Output is correct
4 Correct 2029 ms 229408 KB Output is correct
5 Correct 2076 ms 276220 KB Output is correct
6 Correct 2149 ms 241668 KB Output is correct
7 Correct 126 ms 7180 KB Output is correct
8 Correct 1449 ms 365936 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1536 KB Output is correct
2 Correct 4 ms 1536 KB Output is correct
3 Correct 5 ms 1536 KB Output is correct
4 Correct 4 ms 1664 KB Output is correct
5 Correct 1988 ms 282416 KB Output is correct
6 Correct 2136 ms 282456 KB Output is correct
7 Correct 2015 ms 274932 KB Output is correct
8 Correct 1485 ms 365084 KB Output is correct
9 Correct 125 ms 4344 KB Output is correct
10 Correct 124 ms 4216 KB Output is correct
11 Correct 136 ms 4472 KB Output is correct
12 Correct 129 ms 6412 KB Output is correct
13 Correct 1466 ms 365068 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 896 KB Output is correct
2 Correct 3 ms 1152 KB Output is correct
3 Correct 4 ms 1408 KB Output is correct
4 Correct 5 ms 1536 KB Output is correct
5 Correct 765 ms 131852 KB Output is correct
6 Correct 1274 ms 198860 KB Output is correct
7 Correct 1928 ms 241552 KB Output is correct
8 Correct 2201 ms 279196 KB Output is correct
9 Correct 539 ms 4856 KB Output is correct
10 Correct 626 ms 3708 KB Output is correct
11 Correct 549 ms 4860 KB Output is correct
12 Correct 634 ms 3592 KB Output is correct
13 Correct 547 ms 4852 KB Output is correct
14 Correct 622 ms 3580 KB Output is correct
15 Correct 121 ms 7368 KB Output is correct
16 Correct 1516 ms 365964 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 447 ms 1656 KB Output is correct
9 Correct 494 ms 5588 KB Output is correct
10 Correct 759 ms 14200 KB Output is correct
11 Correct 2029 ms 229408 KB Output is correct
12 Correct 2076 ms 276220 KB Output is correct
13 Correct 2149 ms 241668 KB Output is correct
14 Correct 126 ms 7180 KB Output is correct
15 Correct 1449 ms 365936 KB Output is correct
16 Correct 4 ms 1536 KB Output is correct
17 Correct 4 ms 1536 KB Output is correct
18 Correct 5 ms 1536 KB Output is correct
19 Correct 4 ms 1664 KB Output is correct
20 Correct 1988 ms 282416 KB Output is correct
21 Correct 2136 ms 282456 KB Output is correct
22 Correct 2015 ms 274932 KB Output is correct
23 Correct 1485 ms 365084 KB Output is correct
24 Correct 125 ms 4344 KB Output is correct
25 Correct 124 ms 4216 KB Output is correct
26 Correct 136 ms 4472 KB Output is correct
27 Correct 129 ms 6412 KB Output is correct
28 Correct 1466 ms 365068 KB Output is correct
29 Correct 2 ms 896 KB Output is correct
30 Correct 3 ms 1152 KB Output is correct
31 Correct 4 ms 1408 KB Output is correct
32 Correct 5 ms 1536 KB Output is correct
33 Correct 765 ms 131852 KB Output is correct
34 Correct 1274 ms 198860 KB Output is correct
35 Correct 1928 ms 241552 KB Output is correct
36 Correct 2201 ms 279196 KB Output is correct
37 Correct 539 ms 4856 KB Output is correct
38 Correct 626 ms 3708 KB Output is correct
39 Correct 549 ms 4860 KB Output is correct
40 Correct 634 ms 3592 KB Output is correct
41 Correct 547 ms 4852 KB Output is correct
42 Correct 622 ms 3580 KB Output is correct
43 Correct 121 ms 7368 KB Output is correct
44 Correct 1516 ms 365964 KB Output is correct
45 Correct 250 ms 2936 KB Output is correct
46 Correct 284 ms 3064 KB Output is correct
47 Correct 843 ms 100896 KB Output is correct
48 Correct 1475 ms 229528 KB Output is correct
49 Correct 141 ms 4600 KB Output is correct
50 Correct 132 ms 4728 KB Output is correct
51 Correct 143 ms 4856 KB Output is correct
52 Correct 150 ms 5368 KB Output is correct
53 Correct 133 ms 5112 KB Output is correct
54 Correct 159 ms 5368 KB Output is correct