oj.uz

Submission #743938

# Submission time Handle Problem Language Result Execution time Memory
743938 2023-05-18T06:24:04 Z ThMinh_ Street Lamps (APIO19_street_lamps) C++14
100 / 100
 2119 ms 93040 KB 
#include<bits/stdc++.h>
#define forin(i,a,b) for(int i=a;i<=b;++i)
#define fi first
#define la second
using namespace std;
const int N = 3e5 + 10;
int n, q;
vector<int> bit[N], tr[N];
bool a[N];
set<pair<int, int>> st;
struct query {
    string s;
    int i, a, b;
};
query d[N];
void fakeup(int f, int l) {
    while(f <= n + 1) {
        bit[f].push_back(l);
        f += f & -f;
    }
}
void fakeget(int f, int l) {
    while(f) {
        bit[f].push_back(l);
        f -= f & -f;
    }
}
void up(int f, int l, int val) {
    while(f <= n + 1) {
        int y = lower_bound(bit[f].begin(), bit[f].end(), l) - bit[f].begin() + 1;
        while(y) {
            tr[f][y - 1] += val;
            y -= y & -y;
        }
        f += f & -f;
    }
}
int get(int f, int l) {
    int res = 0;
    while(f) {
        int y = lower_bound(bit[f].begin(), bit[f].end(), l) - bit[f].begin() + 1;
        while(y <= bit[f].size()) {
            res += tr[f][y - 1];
            y += y & -y;
        }
        f -= f & -f;
    }
    return res;
}
void fakeadd(int f, int l) {
    fakeup(f, l + 1);
    st.insert({f, l});
}
void add(int f, int l, int val) {
    up(f, l + 1, val);
    st.insert({f, l});
}
int main () {
    cin.tie(0)->sync_with_stdio(0);
    if(fopen("Task.inp","r")) {
        freopen("Task.inp","r",stdin);
        freopen("WA.out","w",stdout);
    }
    cin>>n>>q;
    string s; cin>>s;
    s = " " + s;
    forin(i,1,n) a[i] = (s[i] == '1');
    int f = -1;
    forin(i,1,n + 1) {
        if(f == -1 && a[i]) f = i;
        if(f != -1 && !a[i]) {
            fakeadd(f, i - 1);
            f = -1;
        }
    }
    st.insert({-1, -1});
    st.insert({1e9, 1e9});
    forin(j,1,q) {
        cin>>d[j].s;
        string s = d[j].s;
        if(s[0] == 't') {
            int i; cin>>i;
            d[j].i = i;
            auto i1 = st.upper_bound({i, 1e9});
            auto i2 = i1--;
            pair<int, int> cur = *i1;
            pair<int, int> aft = *i2;
            if(cur.la + 1 < i && i < aft.fi - 1) fakeadd(i, i);
            else if(i == cur.la + 1 && i == aft.fi - 1) {
                st.erase(i1); fakeup(cur.fi, cur.la + 1);
                st.erase(i2); fakeup(aft.fi, aft.la + 1);
                fakeadd(cur.fi, aft.la);
            }
            else if(i == cur.la + 1) {
                st.erase(i1); fakeup(cur.fi, cur.la + 1);
                fakeadd(cur.fi, cur.la + 1);
            }
            else if(i == aft.fi - 1) {
                st.erase(i2); fakeup(aft.fi, aft.la + 1);
                fakeadd(aft.fi - 1, aft.la);
            }
            else if(i <= cur.la) {
                st.erase(i1); fakeup(cur.fi, cur.la + 1);
                if(cur.fi != aft.la) {
                    if(i == cur.fi) fakeadd(cur.fi + 1, cur.la);
                    else if(i == cur.la) fakeadd(cur.fi, cur.la - 1);
                    else {
                        fakeadd(cur.fi, i - 1);
                        fakeadd(i + 1, cur.la);
                    }
                }
            }
        }
        else {
            cin>>d[j].a>>d[j].b;
            fakeget(d[j].a, d[j].b);
        }
    }
    forin(i,1,n + 1) {
        sort(bit[i].begin(), bit[i].end());
        bit[i].resize(unique(bit[i].begin(), bit[i].end()) - bit[i].begin());
        tr[i].resize(bit[i].size());
    }
    while(!st.empty()) st.erase(st.begin());
    f = -1;
    forin(i,1,n + 1) {
        if(f == -1 && a[i]) f = i;
        if(f != -1 && !a[i]) {
            add(f, i - 1, q);
            f = -1;
        }
    }
    st.insert({-1, -1});
    st.insert({1e9, 1e9});
    forin(j,1,q) {
        string s = d[j].s;
        if(s[0] == 't') {
            int i = d[j].i;
            auto i1 = st.upper_bound({i, 1e9});
            auto i2 = i1--;
            pair<int, int> cur = *i1;
            pair<int, int> aft = *i2;
            int val = q - j;
            if(cur.la + 1 < i && i < aft.fi - 1) add(i, i, val);
            else if(i == cur.la + 1 && i == aft.fi - 1) {
                st.erase(i1); up(cur.fi, cur.la + 1, -val);
                st.erase(i2); up(aft.fi, aft.la + 1, -val);
                add(cur.fi, aft.la, val);
            }
            else if(i == cur.la + 1) {
                st.erase(i1); up(cur.fi, cur.la + 1, -val);
                add(cur.fi, cur.la + 1, val);
            }
            else if(i == aft.fi - 1) {
                st.erase(i2); up(aft.fi, aft.la + 1, -val);
                add(aft.fi - 1, aft.la, val);
            }
            else if(i <= cur.la) {
                st.erase(i1); up(cur.fi, cur.la + 1, -val);
                if(cur.fi != cur.la) {
                    if(i == cur.fi) add(cur.fi + 1, cur.la, val);
                    else if(i == cur.la) add(cur.fi, cur.la - 1, val);
                    else {
                        add(cur.fi, i - 1, val);
                        add(i + 1, cur.la, val);
                    }
                }
            }
        }
        else {
            int a = d[j].a, b = d[j].b;
            pair<int, int> it = *--st.upper_bound({a, 1e9});
            if(it.fi <= a && b <= it.la + 1) cout<<get(a, b) - (q - j)<<"\n";
            else cout<<get(a, b)<<"\n";
        }
    }
}

Compilation message

street_lamps.cpp: In function 'int get(int, int)':
street_lamps.cpp:42:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         while(y <= bit[f].size()) {
      |               ~~^~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen("Task.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen("WA.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28500 KB Output is correct
2 Correct 14 ms 28508 KB Output is correct
3 Correct 14 ms 28412 KB Output is correct
4 Correct 13 ms 28500 KB Output is correct
5 Correct 14 ms 28504 KB Output is correct
6 Correct 15 ms 28508 KB Output is correct
7 Correct 14 ms 28504 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 38628 KB Output is correct
2 Correct 308 ms 40080 KB Output is correct
3 Correct 523 ms 48944 KB Output is correct
4 Correct 1690 ms 82836 KB Output is correct
5 Correct 1631 ms 82212 KB Output is correct
6 Correct 1966 ms 85020 KB Output is correct
7 Correct 884 ms 66456 KB Output is correct
8 Correct 997 ms 67832 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28628 KB Output is correct
2 Correct 16 ms 28516 KB Output is correct
3 Correct 17 ms 28520 KB Output is correct
4 Correct 17 ms 28500 KB Output is correct
5 Correct 2005 ms 83672 KB Output is correct
6 Correct 1807 ms 87236 KB Output is correct
7 Correct 1553 ms 84352 KB Output is correct
8 Correct 821 ms 68288 KB Output is correct
9 Correct 129 ms 35824 KB Output is correct
10 Correct 149 ms 36300 KB Output is correct
11 Correct 140 ms 36520 KB Output is correct
12 Correct 873 ms 66840 KB Output is correct
13 Correct 899 ms 68280 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28512 KB Output is correct
2 Correct 17 ms 28520 KB Output is correct
3 Correct 17 ms 28636 KB Output is correct
4 Correct 19 ms 28640 KB Output is correct
5 Correct 1203 ms 78336 KB Output is correct
6 Correct 1461 ms 82308 KB Output is correct
7 Correct 1696 ms 86124 KB Output is correct
8 Correct 2119 ms 93040 KB Output is correct
9 Correct 444 ms 45104 KB Output is correct
10 Correct 368 ms 42984 KB Output is correct
11 Correct 383 ms 45216 KB Output is correct
12 Correct 318 ms 42772 KB Output is correct
13 Correct 395 ms 45272 KB Output is correct
14 Correct 349 ms 42848 KB Output is correct
15 Correct 887 ms 66876 KB Output is correct
16 Correct 955 ms 68256 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28500 KB Output is correct
2 Correct 14 ms 28508 KB Output is correct
3 Correct 14 ms 28412 KB Output is correct
4 Correct 13 ms 28500 KB Output is correct
5 Correct 14 ms 28504 KB Output is correct
6 Correct 15 ms 28508 KB Output is correct
7 Correct 14 ms 28504 KB Output is correct
8 Correct 247 ms 38628 KB Output is correct
9 Correct 308 ms 40080 KB Output is correct
10 Correct 523 ms 48944 KB Output is correct
11 Correct 1690 ms 82836 KB Output is correct
12 Correct 1631 ms 82212 KB Output is correct
13 Correct 1966 ms 85020 KB Output is correct
14 Correct 884 ms 66456 KB Output is correct
15 Correct 997 ms 67832 KB Output is correct
16 Correct 18 ms 28628 KB Output is correct
17 Correct 16 ms 28516 KB Output is correct
18 Correct 17 ms 28520 KB Output is correct
19 Correct 17 ms 28500 KB Output is correct
20 Correct 2005 ms 83672 KB Output is correct
21 Correct 1807 ms 87236 KB Output is correct
22 Correct 1553 ms 84352 KB Output is correct
23 Correct 821 ms 68288 KB Output is correct
24 Correct 129 ms 35824 KB Output is correct
25 Correct 149 ms 36300 KB Output is correct
26 Correct 140 ms 36520 KB Output is correct
27 Correct 873 ms 66840 KB Output is correct
28 Correct 899 ms 68280 KB Output is correct
29 Correct 16 ms 28512 KB Output is correct
30 Correct 17 ms 28520 KB Output is correct
31 Correct 17 ms 28636 KB Output is correct
32 Correct 19 ms 28640 KB Output is correct
33 Correct 1203 ms 78336 KB Output is correct
34 Correct 1461 ms 82308 KB Output is correct
35 Correct 1696 ms 86124 KB Output is correct
36 Correct 2119 ms 93040 KB Output is correct
37 Correct 444 ms 45104 KB Output is correct
38 Correct 368 ms 42984 KB Output is correct
39 Correct 383 ms 45216 KB Output is correct
40 Correct 318 ms 42772 KB Output is correct
41 Correct 395 ms 45272 KB Output is correct
42 Correct 349 ms 42848 KB Output is correct
43 Correct 887 ms 66876 KB Output is correct
44 Correct 955 ms 68256 KB Output is correct
45 Correct 142 ms 34524 KB Output is correct
46 Correct 199 ms 36484 KB Output is correct
47 Correct 974 ms 56556 KB Output is correct
48 Correct 1890 ms 84712 KB Output is correct
49 Correct 175 ms 36876 KB Output is correct
50 Correct 159 ms 36596 KB Output is correct
51 Correct 164 ms 37304 KB Output is correct
52 Correct 189 ms 39248 KB Output is correct
53 Correct 195 ms 39100 KB Output is correct
54 Correct 190 ms 39124 KB Output is correct