oj.uz

Submission #496438

# Submission time Handle Problem Language Result Execution time Memory
496438 2021-12-21T08:01:09 Z dantoh000 Street Lamps (APIO19_street_lamps) C++14
100 / 100
 770 ms 30020 KB 
#include <bits/stdc++.h>
/// based on https://sltechnicalacademy.com/apio-2019-problems-solutions/
using namespace std;
typedef pair<int,int> ii;
int n,q;
char str[300005];
struct seg{
    int s, e, t;
    bool operator<(const seg &i)const{
		return s < i.s;
	}
};

struct evt{
    int s, e, t, type;
    bool operator<(const evt &i)const{
		return ii(s,e) < ii(i.s,i.e);
	}
};
int ans[300005];
vector<evt> ev;
set<seg> s;
struct fenwick{
    int a[300005];
    void add(int x, int v){
        while (x < 300005){
            a[x] += v;
            x += x&-x;
        }
    }
    int qu(int x){
        int ret = 0;
        while (x){
            ret += a[x];
            x -= x&-x;
        }
        return ret;
    }



}fw;

void solve(int l, int r){
    if (l == r) return;
    //printf("solving (%d %d)\n",l,r);
    int m = (l+r)/2;
    solve(l,m);
    solve(m+1,r);
    vector<evt> up, qu;
    for (int i = l; i <= m; i++){
        //printf("%d %d %d %d %d\n",i,ev[i].s, ev[i].e, ev[i].t, ev[i].type);
        if (ev[i].type == 1){
            up.push_back(ev[i]);
        }
    }
    for (int i = m+1; i <= r; i++){
        //printf("%d %d %d %d %d\n",i,ev[i].s, ev[i].e, ev[i].t, ev[i].type);
        if (ev[i].type == 2){
            qu.push_back(ev[i]);
        }
    }
    for (auto x : up){
        //printf("update %d %d %d\n",x.s,x.e,x.t);
    }
    for (auto x : qu){
        //printf("query %d %d %d\n",x.s,x.e,x.t);
    }
    sort(up.begin(),up.end());
    sort(qu.begin(),qu.end());
    int i = 0;
    for (auto Q : qu){
        while (i < up.size() && up[i].s <= Q.s){
            fw.add(up[i].e, up[i].t);
            i++;
        }
        ans[Q.t] += fw.qu(Q.e);
    }
    for (int j = 0; j < i; j++){
        fw.add(up[j].e, -up[j].t);
    }
    //printf("end solve (%d %d)\n",l,r);

}
void addrange(int s, int e, int v){
    ev.push_back({s,s,v,1});
    ev.push_back({s,e+1,-v,1});
}




int main(){
    scanf("%d%d", &n,&q);
    scanf("%s",str+1);
    for (int i = 1; i <= n; i++){
        if (str[i] == '1'){
            int e = i;
            while (e <= n && str[e] == '1') e++;
            s.insert({i,e-1,0});
            i = e-1;
        }
    }
    for (int i = 0; i < q; i++){
        string Qs;
        cin >> Qs;
        if (Qs == "toggle"){
            int x; scanf("%d",&x);
            if (str[x] == '0'){
                int st = x, ed = x;
                auto it = s.lower_bound({x+1, -1, -1});
                if (it != s.end() && it->s == x+1){
                    addrange(it->s, it->e, i+1 - it->t);
                    ed = it->e;
                    it = s.erase(it);
                }
                if (it != s.begin() && prev(it)->e == x-1){
                    --it;
                    addrange(it->s, it->e, i+1 - it->t);
                    st = it->s;
                    it = s.erase(it);
                }
                s.insert({st,ed,i+1});
            }
            else{
                auto it = --s.lower_bound({x+1, -1, -1});
                addrange(it->s, it->e, i+1 - it->t);
                int S = it->s;
                int E = it->e;
                s.erase(it);
                if (S < x) s.insert({S,x-1,i+1});
                if (x < E) s.insert({x+1,E,i+1});
            }
            str[x] ^= 1;
            ans[i] = -1;
        }
        else{
            int a,b; scanf("%d%d",&a,&b);
            b--;
            ev.push_back({a,b,i,2});
            auto it = s.lower_bound({a+1,-1,-1});
            if (it != s.begin()){
                --it;
                if (it->s <= a && b <= it->e){
                    //printf("found existing range %d %d %d\n",it->s,it->e,it->t);
                    ans[i] += i+1-it->t;
                }
            }
        }
    }
    solve(0, ev.size()-1);
    for (int i = 0; i < q; i++){
        if (ans[i] != -1) printf("%d\n",ans[i]);
    }


}

Compilation message

street_lamps.cpp: In function 'void solve(int, int)':
street_lamps.cpp:63:15: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   63 |     for (auto x : up){
      |               ^
street_lamps.cpp:66:15: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   66 |     for (auto x : qu){
      |               ^
street_lamps.cpp:73:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<evt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         while (i < up.size() && up[i].s <= Q.s){
      |                ~~^~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |     scanf("%d%d", &n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |     scanf("%s",str+1);
      |     ~~~~~^~~~~~~~~~~~
street_lamps.cpp:108:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |             int x; scanf("%d",&x);
      |                    ~~~~~^~~~~~~~~
street_lamps.cpp:138:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |             int a,b; scanf("%d%d",&a,&b);
      |                      ~~~~~^~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 14948 KB Output is correct
2 Correct 564 ms 15084 KB Output is correct
3 Correct 589 ms 15216 KB Output is correct
4 Correct 646 ms 21288 KB Output is correct
5 Correct 722 ms 22668 KB Output is correct
6 Correct 565 ms 22996 KB Output is correct
7 Correct 340 ms 12928 KB Output is correct
8 Correct 334 ms 12912 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 660 ms 27124 KB Output is correct
6 Correct 770 ms 27340 KB Output is correct
7 Correct 730 ms 22748 KB Output is correct
8 Correct 378 ms 12860 KB Output is correct
9 Correct 201 ms 9028 KB Output is correct
10 Correct 234 ms 11736 KB Output is correct
11 Correct 239 ms 11720 KB Output is correct
12 Correct 370 ms 12856 KB Output is correct
13 Correct 374 ms 12924 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 474 ms 18864 KB Output is correct
6 Correct 526 ms 23708 KB Output is correct
7 Correct 597 ms 22892 KB Output is correct
8 Correct 608 ms 30020 KB Output is correct
9 Correct 463 ms 17676 KB Output is correct
10 Correct 480 ms 23720 KB Output is correct
11 Correct 465 ms 17828 KB Output is correct
12 Correct 481 ms 23560 KB Output is correct
13 Correct 483 ms 17884 KB Output is correct
14 Correct 475 ms 23736 KB Output is correct
15 Correct 370 ms 12856 KB Output is correct
16 Correct 374 ms 12896 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 552 ms 14948 KB Output is correct
9 Correct 564 ms 15084 KB Output is correct
10 Correct 589 ms 15216 KB Output is correct
11 Correct 646 ms 21288 KB Output is correct
12 Correct 722 ms 22668 KB Output is correct
13 Correct 565 ms 22996 KB Output is correct
14 Correct 340 ms 12928 KB Output is correct
15 Correct 334 ms 12912 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 2 ms 460 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 660 ms 27124 KB Output is correct
21 Correct 770 ms 27340 KB Output is correct
22 Correct 730 ms 22748 KB Output is correct
23 Correct 378 ms 12860 KB Output is correct
24 Correct 201 ms 9028 KB Output is correct
25 Correct 234 ms 11736 KB Output is correct
26 Correct 239 ms 11720 KB Output is correct
27 Correct 370 ms 12856 KB Output is correct
28 Correct 374 ms 12924 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 1 ms 332 KB Output is correct
32 Correct 2 ms 332 KB Output is correct
33 Correct 474 ms 18864 KB Output is correct
34 Correct 526 ms 23708 KB Output is correct
35 Correct 597 ms 22892 KB Output is correct
36 Correct 608 ms 30020 KB Output is correct
37 Correct 463 ms 17676 KB Output is correct
38 Correct 480 ms 23720 KB Output is correct
39 Correct 465 ms 17828 KB Output is correct
40 Correct 481 ms 23560 KB Output is correct
41 Correct 483 ms 17884 KB Output is correct
42 Correct 475 ms 23736 KB Output is correct
43 Correct 370 ms 12856 KB Output is correct
44 Correct 374 ms 12896 KB Output is correct
45 Correct 366 ms 9632 KB Output is correct
46 Correct 362 ms 9816 KB Output is correct
47 Correct 381 ms 11680 KB Output is correct
48 Correct 663 ms 21124 KB Output is correct
49 Correct 250 ms 12572 KB Output is correct
50 Correct 263 ms 12700 KB Output is correct
51 Correct 249 ms 12556 KB Output is correct
52 Correct 242 ms 12672 KB Output is correct
53 Correct 248 ms 12684 KB Output is correct
54 Correct 241 ms 12664 KB Output is correct