oj.uz

답안 #722685

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
722685 2023-04-12T15:39:57 Z victor_gao 가로등 (APIO19_street_lamps) C++17
100 / 100
 3062 ms 212516 KB 
//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 300015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
struct BIT{
    int n;
    vector<int>arr;
    vector<int>have;
    void in(int x){ have.push_back(x); }
    void build(){
        sort(have.begin(),have.end());
        have.resize(unique(have.begin(),have.end())-have.begin());
        n=have.size();
        arr.resize(n+3);
    }
    int idx(int x){ 
        if (have.empty()) return 0;
        return upper_bound(have.begin(),have.end(),x)-have.begin();
    }
    void modify(int p,int c){
        if (p==0) return;
        for (;p<=n;p+=(p&-p))
            arr[p]+=c;
    }
    int query(int p){
        int ans=0;
        for (;p>0;p-=(p&-p))
            ans+=arr[p];
        return ans;
    }
};
struct BBIT{
    int n;
    vector<BIT>arr;
    void init(int _n){
        n=_n;
        arr.resize(n+3);
    }
    void need_use(int a,int b){
        for (;a<=n;a+=(a&-a))
            arr[a].in(b);
    }
    void modify(int a,int b,int c){
        for (;a<=n;a+=(a&-a))
            arr[a].modify(arr[a].idx(b),c);
    }
    int query(int a,int b){
        int ans=0;
        for (;a>0;a-=(a&-a))
            ans=(ans+arr[a].query(arr[a].idx(b)));
        return ans;
    }
}bit;
struct Query{
    int op,a,b;
    Query(int i,int j,int k):op(i),a(j),b(k){}
};
int n,q,last_time[N];
bool arr[N];
set<pair<pii,int> >all;
vector<Query>qry;
vector<pair<pii,int> >change[N];
void add_need(int a,int b){
    if (a>b) return;
    bit.need_use(a,a); bit.need_use(a,b+1);
    bit.need_use(b+1,a); bit.need_use(b+1,b+1);
}
signed main(){
    fast
    cin>>n>>q;
    bit.init(n);
    int l=1,val=-1;
    for (int i=1;i<=n;i++){
        char c; cin>>c;
        arr[i]=c-'0';
        if (arr[i]==val) continue;
        else {
            if (val==1) all.insert({{l,i-1},0});
            val=arr[i]; l=i;
        }
    }
    if (val==1)
        all.insert({{l,n},0});
    for (int i=1;i<=q;i++){
        string str;
        int a=0,b=0; cin>>str;
        if (str=="toggle"){
            cin>>a;
            qry.push_back(Query(1,a,a));
        }
        else {
            cin>>a>>b; b--;
            qry.push_back(Query(2,a,b));
            bit.need_use(a,b);
        }
    }
    for (int i=1;i<=q;i++){
        if (qry[i-1].op==1){
            int p=qry[i-1].a;
            if (arr[p]==1){
                auto it=all.upper_bound(pair<pii,int>(pii(p,1e9),1e9)); it--;
                auto [j,t]=(*it);
                change[i].push_back({{j.x,j.y},i-t});
                add_need(j.x,j.y);
                all.erase(it);
                if (j.x<=p-1) all.insert({{j.x,p-1},i});
                if (p+1<=j.y) all.insert({{p+1,j.y},i});
            }
            else {
                auto it=all.upper_bound(pair<pii,int>(pii(p,p),1e9));
                pii now={p,p};
                if (it!=all.end()){
                    if ((*it).x.x==p+1){
                        now.y=(*it).x.y;
                        change[i].push_back({(*it).x,i-(*it).y});
                        add_need((*it).x.x,(*it).x.y);
                        it=all.erase(it);
                    }
                }
                if (it!=all.begin()){
                    it=prev(it);
                    if ((*it).x.y==p-1){
                        now.x=(*it).x.x;
                        change[i].push_back({(*it).x,i-(*it).y});
                        add_need((*it).x.x,(*it).x.y);
                        it=all.erase(it);
                    }
                }
                all.insert({now,i});
            }
            arr[p]^=1;
        }
        else {
            int a=qry[i-1].a,b=qry[i-1].b;
            auto it=all.upper_bound(pair<pii,int>(pii(a,1e9),1e9));
            if (it==all.begin()){
                last_time[i]=i;
                continue;
            }
            it--;
            if ((*it).x.x<=a&&(*it).x.y>=b) last_time[i]=(*it).y;
            else last_time[i]=i;
        }
    }
    for (int i=0;i<=n+1;i++)
        bit.arr[i].build();
    for (int i=1;i<=q;i++){
        if (qry[i-1].op==1){
            for (auto [j,t]:change[i]){
               // cout<<"change "<<j.x<<' '<<j.y<<" "<<t<<'\n';
                bit.modify(j.x,j.x,t);
                bit.modify(j.x,j.y+1,-t);
                bit.modify(j.y+1,j.x,-t);
                bit.modify(j.y+1,j.y+1,t);
            }
        }
        else {
            cout<<bit.query(qry[i-1].a,qry[i-1].b)+i-last_time[i]<<'\n';
        }
    }
}
/*
5 7
11111
query 1 2
toggle 4
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 5 ms 7380 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 346 ms 45332 KB Output is correct
2 Correct 471 ms 62772 KB Output is correct
3 Correct 787 ms 82652 KB Output is correct
4 Correct 1964 ms 160852 KB Output is correct
5 Correct 2501 ms 172832 KB Output is correct
6 Correct 2174 ms 166436 KB Output is correct
7 Correct 780 ms 97744 KB Output is correct
8 Correct 784 ms 99608 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 7764 KB Output is correct
2 Correct 7 ms 7792 KB Output is correct
3 Correct 6 ms 7764 KB Output is correct
4 Correct 5 ms 7508 KB Output is correct
5 Correct 2775 ms 212516 KB Output is correct
6 Correct 3062 ms 205552 KB Output is correct
7 Correct 2590 ms 175384 KB Output is correct
8 Correct 1130 ms 101628 KB Output is correct
9 Correct 134 ms 25904 KB Output is correct
10 Correct 147 ms 33840 KB Output is correct
11 Correct 179 ms 34944 KB Output is correct
12 Correct 1098 ms 105932 KB Output is correct
13 Correct 1122 ms 107368 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 7568 KB Output is correct
2 Correct 5 ms 7636 KB Output is correct
3 Correct 6 ms 7764 KB Output is correct
4 Correct 8 ms 7828 KB Output is correct
5 Correct 1225 ms 105940 KB Output is correct
6 Correct 1687 ms 138092 KB Output is correct
7 Correct 2218 ms 165656 KB Output is correct
8 Correct 2798 ms 195848 KB Output is correct
9 Correct 576 ms 70832 KB Output is correct
10 Correct 435 ms 65660 KB Output is correct
11 Correct 559 ms 74404 KB Output is correct
12 Correct 494 ms 68900 KB Output is correct
13 Correct 616 ms 74048 KB Output is correct
14 Correct 467 ms 67360 KB Output is correct
15 Correct 1082 ms 105868 KB Output is correct
16 Correct 1061 ms 107448 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 5 ms 7380 KB Output is correct
8 Correct 346 ms 45332 KB Output is correct
9 Correct 471 ms 62772 KB Output is correct
10 Correct 787 ms 82652 KB Output is correct
11 Correct 1964 ms 160852 KB Output is correct
12 Correct 2501 ms 172832 KB Output is correct
13 Correct 2174 ms 166436 KB Output is correct
14 Correct 780 ms 97744 KB Output is correct
15 Correct 784 ms 99608 KB Output is correct
16 Correct 7 ms 7764 KB Output is correct
17 Correct 7 ms 7792 KB Output is correct
18 Correct 6 ms 7764 KB Output is correct
19 Correct 5 ms 7508 KB Output is correct
20 Correct 2775 ms 212516 KB Output is correct
21 Correct 3062 ms 205552 KB Output is correct
22 Correct 2590 ms 175384 KB Output is correct
23 Correct 1130 ms 101628 KB Output is correct
24 Correct 134 ms 25904 KB Output is correct
25 Correct 147 ms 33840 KB Output is correct
26 Correct 179 ms 34944 KB Output is correct
27 Correct 1098 ms 105932 KB Output is correct
28 Correct 1122 ms 107368 KB Output is correct
29 Correct 6 ms 7568 KB Output is correct
30 Correct 5 ms 7636 KB Output is correct
31 Correct 6 ms 7764 KB Output is correct
32 Correct 8 ms 7828 KB Output is correct
33 Correct 1225 ms 105940 KB Output is correct
34 Correct 1687 ms 138092 KB Output is correct
35 Correct 2218 ms 165656 KB Output is correct
36 Correct 2798 ms 195848 KB Output is correct
37 Correct 576 ms 70832 KB Output is correct
38 Correct 435 ms 65660 KB Output is correct
39 Correct 559 ms 74404 KB Output is correct
40 Correct 494 ms 68900 KB Output is correct
41 Correct 616 ms 74048 KB Output is correct
42 Correct 467 ms 67360 KB Output is correct
43 Correct 1082 ms 105868 KB Output is correct
44 Correct 1061 ms 107448 KB Output is correct
45 Correct 154 ms 29300 KB Output is correct
46 Correct 254 ms 38556 KB Output is correct
47 Correct 1140 ms 90736 KB Output is correct
48 Correct 2283 ms 164600 KB Output is correct
49 Correct 175 ms 34460 KB Output is correct
50 Correct 164 ms 34732 KB Output is correct
51 Correct 189 ms 36212 KB Output is correct
52 Correct 205 ms 37352 KB Output is correct
53 Correct 210 ms 37240 KB Output is correct
54 Correct 203 ms 37356 KB Output is correct