oj.uz

Submission #933757

# Submission time Handle Problem Language Result Execution time Memory
933757 2024-02-26T09:13:41 Z VinhLuu Street Lamps (APIO19_street_lamps) C++17
100 / 100
 1269 ms 143584 KB 
// REPUTATION RATING =

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()
using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 3e5 + 5;
//const int oo = 1e9;
const int mod = 1e9 + 7;

int n, q, a[N], L[N], R[N], X[N];
string s, T[N];

namespace sub1{
    int m[105][105];
    void solve(){
        for(int i = 1; i <= n; i ++) m[1][i] = a[i];
        for(int t = 1; t <= q; t ++){
            string type; cin >> type;
            if(type[0] == 't'){
                int x; cin >> x;
                a[x] = 1 - a[x];
            }else{
                int l, r, ans = 0; cin >> l >> r;
                for(int j = 1; j <= t; j ++){
                    bool ff = true;
                    for(int i = l; i < r; i ++) if(m[j][i] == 0){
                        ff = false;
                        break;
                    }
                    ans += ff;
                }
                cout << ans << "\n";
            }
            for(int i = 1;i <= n; i ++) m[t + 1][i] = a[i];
        }
    }
}

namespace sub5{
    int op[N];
    int time[N], kq[N], tup[N], t;
    struct Q{
        int l,r,w;
    } query[N];

    vector<int> node[N], BIT[N];

    void fakeupdate(int x,int y){
        for(; x <= n; x += x & -x) node[x].pb(y);
    }

    void fakeGet(int x,int y){
        for(; x > 0; x -= x & -x) node[x].pb(y);
    }

    void FGet(int x,int y,int i,int j){
        fakeGet(x - 1, y - 1);
        fakeGet(x - 1, j);
        fakeGet(i, y - 1);
        fakeGet(i, j);
    }

    void update(int x, int yy, int val) {
        for (; x <= n; x += x & -x)
            for (int y = lower_bound(node[x].begin(), node[x].end(), yy) - node[x].begin() + 1; y <= node[x].size(); y += y & -y)  //tìm vị trí sau khi rời rạc
                BIT[x][y - 1] += val;
    }

    int get(int x, int yy) {
        int res = 0;
        for (; x > 0; x -= x & -x)
            for (int y = lower_bound(node[x].begin(), node[x].end(), yy) - node[x].begin() + 1; y > 0; y -= y & -y)
                res += BIT[x][y - 1];
        return res;
    }

    int GET(int x,int y,int i,int j){
        return get(i, j) - get(x - 1, j) - get(i, y - 1) + get(x - 1, y - 1);
    }

    void solve(){
        set<int> s;
        s.insert(0);
        s.insert(n + 1);
        time[0] = 1;
        time[n + 1] = 1;
        for(int i = 1; i <= n; i ++){
            op[i] = a[i];
            if(!a[i]){
                s.insert(i);
                time[i] = 1;
            }
        }
        for(int i = 1;i <= q; i ++){
            string type = T[i];
            if(type[0] == 't'){
                int x = X[i];
                if(op[x]){
                    auto j = s.lower_bound(x);
                    int ri = (*j);
                    j--;
                    int le = (*j);
                    if(le + 1 <= ri - 1){
                        tup[i]++;
                        query[++t] = {le + 1, ri - 1, i - time[le] + 1};
                        fakeupdate(le + 1, ri - 1);
//                        cout << le + 1 <<" " << ri - 1 << " " << i - time[le] + 1 << "f\n";
                    }
                    time[le] = i + 1;
                    time[x] = i + 1;
                    s.insert(x);
                }else{
                    auto j = s.lower_bound(x);
                    j--;
                    int le = (*j);
                    j = s.upper_bound(x);
                    int ri = (*j);
//                    cout << x << " " << le << " " << ri << "f\n";
                    if(le + 1 <= x - 1){
                        tup[i]++;
                        query[++t] = {le + 1, x - 1, i - time[le] + 1};
                        fakeupdate(le + 1, x - 1);
                    }
                    if(x + 1 <= ri - 1){
                        tup[i]++;
                        query[++t] = {x + 1, ri - 1, i - time[x] + 1};
                        fakeupdate(x + 1, ri - 1);
//                        cout << x + 1 << " " << ri - 1 << "d\n";
                    }
                    time[le] = i + 1;

                    s.erase(x);
                }

                op[x] = 1 - op[x];
//                for(auto j : s) cout << j << " ";
//                cout << "\n";
            }else{
                int l = L[i], r = R[i];
                auto j = s.lower_bound(l);
//                cerr << i << " " << l << " " << r << " " << (*j) << "r\n";
                if((*j) > r){
                    if((*j) > l) j--;
//                    cerr << (*j) << " " << time[(*j)] << "g\n";
                    kq[i] = i - time[(*j)] + 1;
                }
                FGet(1, r, l, n);
            }

//            for(auto j : s) cout << j << " ";
//            cout << time[0] << "\n";
        }

        for(int i = 1; i <= n; i ++){
            sort(all(node[i]));
            node[i].resize(unique(all(node[i])) - node[i].begin());
            for(auto j : node[i]) BIT[i].pb(0);
        }
        t = 1;
        for(int i = 1;i <= q; i ++){
            string type = T[i];
            if(type[0] == 't'){
                int x = X[i];
                while(tup[i]--){
                    int l = query[t].l, r = query[t].r, w = query[t].w;
                    update(l, r, w);
//                    cout << l << " " << r << " " << w << "d\n";
                    t++;
                }
            }else{
                int l = L[i], r = R[i];
//                cout << 1 << " " << r << " " << l << " " << n << " " << "g\n";
                cout << GET(1, r, l, n) + kq[i] << "\n";

            }
//            cerr << i << "f\n";
        }
//        cerr << "d\n";
        exit(0);
    }
}

#define LOCAL

#ifdef LOCAL
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    #define task "v"
    if(fopen(task ".inp","r")){
        freopen(task ".inp","r",stdin);
        freopen(task ".out","w",stdout);
    }

    cin >> n >> q >> s;
    for(int i = 1; i <= n; i ++) a[i] = s[i - 1] - '0';
//    if(n <= 100 && q <= 100){
//        sub1 :: solve();
//    }
    for(int i = 1; i <= q; i ++) {
        cin >> T[i];
        if(T[i][0] == 't') cin >> X[i];
        else{
            cin >> L[i] >> R[i];
            R[i]--;
        }
    }
    sub5 :: solve();
}
#endif // LOCAL

Compilation message

street_lamps.cpp: In function 'void sub5::update(long long int, long long int, long long int)':
street_lamps.cpp:73:99: 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]
   73 |             for (int y = lower_bound(node[x].begin(), node[x].end(), yy) - node[x].begin() + 1; y <= node[x].size(); y += y & -y)  //tìm vị trí sau khi rời rạc
      |                                                                                                 ~~^~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'void sub5::solve()':
street_lamps.cpp:165:22: warning: unused variable 'j' [-Wunused-variable]
  165 |             for(auto j : node[i]) BIT[i].pb(0);
      |                      ^
street_lamps.cpp:171:21: warning: unused variable 'x' [-Wunused-variable]
  171 |                 int x = X[i];
      |                     ^
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:199:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  199 |         freopen(task ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:200:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  200 |         freopen(task ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 43612 KB Output is correct
2 Correct 11 ms 43612 KB Output is correct
3 Correct 9 ms 43644 KB Output is correct
4 Correct 9 ms 41560 KB Output is correct
5 Correct 8 ms 43612 KB Output is correct
6 Correct 9 ms 41672 KB Output is correct
7 Correct 9 ms 43720 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 67160 KB Output is correct
2 Correct 203 ms 69872 KB Output is correct
3 Correct 363 ms 80508 KB Output is correct
4 Correct 1124 ms 128684 KB Output is correct
5 Correct 1265 ms 131548 KB Output is correct
6 Correct 1027 ms 124820 KB Output is correct
7 Correct 1196 ms 142032 KB Output is correct
8 Correct 1002 ms 131532 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 41804 KB Output is correct
2 Correct 9 ms 43728 KB Output is correct
3 Correct 9 ms 43868 KB Output is correct
4 Correct 9 ms 43868 KB Output is correct
5 Correct 1109 ms 116056 KB Output is correct
6 Correct 1254 ms 128032 KB Output is correct
7 Correct 1269 ms 138264 KB Output is correct
8 Correct 1065 ms 133060 KB Output is correct
9 Correct 126 ms 61316 KB Output is correct
10 Correct 137 ms 62056 KB Output is correct
11 Correct 147 ms 62880 KB Output is correct
12 Correct 1251 ms 143388 KB Output is correct
13 Correct 1050 ms 133060 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 43868 KB Output is correct
2 Correct 10 ms 43696 KB Output is correct
3 Correct 10 ms 43868 KB Output is correct
4 Correct 9 ms 41564 KB Output is correct
5 Correct 1137 ms 138296 KB Output is correct
6 Correct 1101 ms 133420 KB Output is correct
7 Correct 1059 ms 124980 KB Output is correct
8 Correct 1056 ms 115872 KB Output is correct
9 Correct 210 ms 69976 KB Output is correct
10 Correct 143 ms 63028 KB Output is correct
11 Correct 217 ms 69952 KB Output is correct
12 Correct 146 ms 63024 KB Output is correct
13 Correct 215 ms 70068 KB Output is correct
14 Correct 144 ms 63156 KB Output is correct
15 Correct 1243 ms 143584 KB Output is correct
16 Correct 1043 ms 132780 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 43612 KB Output is correct
2 Correct 11 ms 43612 KB Output is correct
3 Correct 9 ms 43644 KB Output is correct
4 Correct 9 ms 41560 KB Output is correct
5 Correct 8 ms 43612 KB Output is correct
6 Correct 9 ms 41672 KB Output is correct
7 Correct 9 ms 43720 KB Output is correct
8 Correct 166 ms 67160 KB Output is correct
9 Correct 203 ms 69872 KB Output is correct
10 Correct 363 ms 80508 KB Output is correct
11 Correct 1124 ms 128684 KB Output is correct
12 Correct 1265 ms 131548 KB Output is correct
13 Correct 1027 ms 124820 KB Output is correct
14 Correct 1196 ms 142032 KB Output is correct
15 Correct 1002 ms 131532 KB Output is correct
16 Correct 9 ms 41804 KB Output is correct
17 Correct 9 ms 43728 KB Output is correct
18 Correct 9 ms 43868 KB Output is correct
19 Correct 9 ms 43868 KB Output is correct
20 Correct 1109 ms 116056 KB Output is correct
21 Correct 1254 ms 128032 KB Output is correct
22 Correct 1269 ms 138264 KB Output is correct
23 Correct 1065 ms 133060 KB Output is correct
24 Correct 126 ms 61316 KB Output is correct
25 Correct 137 ms 62056 KB Output is correct
26 Correct 147 ms 62880 KB Output is correct
27 Correct 1251 ms 143388 KB Output is correct
28 Correct 1050 ms 133060 KB Output is correct
29 Correct 11 ms 43868 KB Output is correct
30 Correct 10 ms 43696 KB Output is correct
31 Correct 10 ms 43868 KB Output is correct
32 Correct 9 ms 41564 KB Output is correct
33 Correct 1137 ms 138296 KB Output is correct
34 Correct 1101 ms 133420 KB Output is correct
35 Correct 1059 ms 124980 KB Output is correct
36 Correct 1056 ms 115872 KB Output is correct
37 Correct 210 ms 69976 KB Output is correct
38 Correct 143 ms 63028 KB Output is correct
39 Correct 217 ms 69952 KB Output is correct
40 Correct 146 ms 63024 KB Output is correct
41 Correct 215 ms 70068 KB Output is correct
42 Correct 144 ms 63156 KB Output is correct
43 Correct 1243 ms 143584 KB Output is correct
44 Correct 1043 ms 132780 KB Output is correct
45 Correct 76 ms 53168 KB Output is correct
46 Correct 121 ms 57412 KB Output is correct
47 Correct 540 ms 91824 KB Output is correct
48 Correct 1154 ms 131016 KB Output is correct
49 Correct 153 ms 64360 KB Output is correct
50 Correct 153 ms 63720 KB Output is correct
51 Correct 162 ms 65328 KB Output is correct
52 Correct 207 ms 70956 KB Output is correct
53 Correct 201 ms 70848 KB Output is correct
54 Correct 201 ms 70960 KB Output is correct