제출 #1162750

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1162750		adhityamv	가로등 (APIO19_street_lamps)	C++20	100 / 100	2987 ms	144588 KiB

street_lamps

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
#include <stack>
using namespace std;
#define int long long
#define mp make_pair
#define fi first
#define pii pair<int,int>
#define se second
const int INF=1000000000000000000;
//const int INF=1e9;
const int N=1000000;
const int M=7+1e9;
const int ln=20;
struct Mint{   
    int n;
    Mint(int nn){
        n=nn%M;
    }
    Mint(){
        n=0;
    }
    Mint& operator+=(Mint const& m){
        n=(n+m.n)%M;
        return *this;
    }
    Mint& operator*=(Mint const& m){
        n=(n*m.n)%M;
        return *this;
    }
    Mint& operator-=(Mint const& m){
        n=(n+M-m.n)%M;
        return *this;
    }
    friend Mint binpow(Mint a,int b){
        if(b==0) return Mint(1);
        Mint r=binpow(a,b/2LL);
        r*=r;
        if(b%2==0) return r;
        r*=a;
        return r;
    }
    friend Mint inverse(Mint a){
        return binpow(a,M-2);
    }
    Mint& operator/=(Mint const &b){
        return (*this)*=inverse(b);
    }
    friend Mint operator+(Mint a,Mint const b){
        return (a+=b);
    }
    friend Mint operator-(Mint a,Mint const b){
        return (a-=b);
    }
    friend Mint operator*(Mint a,Mint const b){
        return (a*=b);
    }
    friend Mint operator/(Mint a,Mint const b){
        return (a/=b);
    }
    friend Mint operator-(Mint a){
        return 0-a;
    }
    friend std::ostream& operator<<(std::ostream& os, Mint const& a){
        return os << a.n;
    }
    friend std::istream& operator>>(std::istream& is, Mint& a){
        return (is >> a.n);
    }
    friend bool operator==(Mint const& a,Mint const& b){
        return a.n==b.n;
    }
    friend bool operator!=(Mint const& a,Mint const& b){
        return a.n!=b.n;
    }
};
template<typename T>
std::ostream& operator<< (std::ostream& os,pair<T,T> p){
    return os << p.fi << " " << p.se << "\n";
}
struct fenwick{
    int n;
    vector<int> bit;
    vector<int> a;
    fenwick(int nn){
        n=nn;
        for(int i=0;i<=n;i++){
            bit.push_back(0);
        }
        for(int i=0;i<n;i++){
            a.push_back(0);
        }
    }
    void update(int i,int val){
        i++;
        while(i<=n){
            bit[i]+=val;
            i+=(i&(-i));
        }
    }
    int query(int i){
        int ans=0;
        while(i>0){
            ans+=bit[i];
            i-=(i&(-i));
        }
        return ans;
    }
};
struct Point{
    int x,y,z;
    int tind;
    int ind;
    int val;
    Point(){
        x=y=z=0;
        ind=0;
        val=0;
    }
    Point(int xx,int yy,int vval){
        x=xx;
        y=yy;
        z=0;
        ind=0;
        val=vval;
        tind=-1;
    }
    Point(int xx,int yy,int zz,int vval){
        x=xx;
        y=yy;
        z=zz;
        ind=0;
        val=vval;
        tind=-1;
    }
    friend bool operator< (Point p1,Point p2){
        return mp(mp(p1.x,p1.y),p1.z)< mp(mp(p2.x,p2.y),p2.z);
    }
};
vector<Point> pts;
vector<int> ans;
fenwick bit(N);
void dnc(int l,int r){
    // if all xs are equal then nothing
    if(pts[l].x==pts[r].x){
        return;
    }
    int mval=(pts[l].x+pts[r].x)/2;
    int m=l;
    while(pts[m].x<=mval) m++;
    m--;
    dnc(l,m);
    dnc(m+1,r);
    // update y after queries at y
    sort(pts.begin()+l,pts.begin()+r+1,[&] (Point p1,Point p2){
        return mp(p1.y,p1.z)<mp(p2.y,p2.z);
    });
    stack<int> toup;
    for(int i=l;i<=r;i++){
        if(pts[i].ind>m){
            if(pts[i].tind!=-1) ans[pts[i].tind]+=bit.query(pts[i].z);
        }
        else {
            toup.push(i);
        }
        if(i==r || pts[i].y<pts[i+1].y){
            while(!toup.empty()){
                int cind=toup.top();
                toup.pop();
                bit.update(pts[cind].z,pts[cind].val);
            }
        }
    }
    sort(pts.begin()+l,pts.begin()+r+1,[&] (Point p1,Point p2){
        return (p1.ind<p2.ind);
    });
    for(int i=l;i<=m;i++){
        bit.update(pts[i].z,-pts[i].val);
    }
}
void getans(){
    int n=pts.size();
    sort(pts.begin(),pts.end());
    //for(int i=0;i<n;i++){
    //    cout << pts[i].x << " " << pts[i].y << " " << pts[i].z << " " << pts[i].val << " " << pts[i].tind << "\n";
    //}
    for(int i=0;i<n;i++) pts[i].ind=i;
    for(int i=0;i<n;i++) ans.push_back(0);
    dnc(0,n-1);
    //cout << ans[0] << "\n";
}
vector<int> a;
struct segtree{
    int n;
    bool rs;
    vector<int> seg;
    segtree(bool rss){
        rs=rss;
        n=a.size();
        for(int i=0;i<2*n;i++) seg.push_back(0);
        for(int i=0;i<n;i++){
            if(a[i]==0) seg[i+n]=i;
            else if(rs) seg[i+n]=-1;
            else seg[i+n]=n;
        }
        for(int i=n-1;i>0;i--){
            if(rs) seg[i]=max(seg[2*i],seg[2*i+1]);
            else seg[i]=min(seg[2*i],seg[2*i+1]);
        }
    }
    void update(int i,int val){
        a[i]=val;
        if(a[i]==0) seg[i+n]=i;
        else if(rs) seg[i+n]=-1;
        else seg[i+n]=n;
        i+=n;
        while(i>1){
            if(rs) seg[i>>1]=max(seg[i],seg[i^1]);
            else seg[i>>1]=min(seg[i],seg[i^1]);
            i>>=1;
        }
    }
    int query(int l,int r){
        l+=n;
        r+=n;
        int ans=n;
        if(rs) ans=-1;
        while(l<r){
            if(l&1){
                if(rs) ans=max(ans,seg[l++]);
                else ans=min(ans,seg[l++]);
            }
            if(r&1){
                if(rs) ans=max(ans,seg[--r]);
                else ans=min(ans,seg[--r]);
            }
            l>>=1;
            r>>=1;

        }
        return ans;
    }
};
void solve(){
    int n,q;
    cin >> n >> q;
    string s;
    cin >> s;
    for(int i=0;i<n;i++){
        a.push_back(s[i]-'0');
    }
    segtree ls(false);
    segtree rs(true);
    segtree lls(false);
    segtree rrs(true);
    // when doing an update from 0 to 1
    // some cells get ++ for the validity time of an interval
    // suppose leftmost 1 is l, rightmost 1 is r
    // then all l<=x,y<=r ++
    // answer for x,y will be sum over xi<x+1,yi<y+1
    // so got to update (r+1,r+1) to -1, (l,r+1) and (r+1,l) to 1, (l,l) to -1
    // so we should get the l and r
    int tind=0;
    vector<int> ex;
    for(int ii=0;ii<q;ii++){
        string tpe;
        cin >> tpe;
        if(tpe=="toggle"){
            int i;
            cin >> i;
            i--;
            if(a[i]==0){
                ls.update(i,1);
                rs.update(i,1);
                int l=rs.query(0,i+1);
                l++;
                int r=ls.query(i,n);
                r--;
                // l to i and i to r
                pts.push_back(Point(l,i,ii,-ii));
                pts.push_back(Point(l,r+1,ii,ii));
                pts.push_back(Point(i+1,i,ii,ii));
                pts.push_back(Point(i+1,r+1,ii,-ii));
            } else{
                int l=rs.query(0,i+1);
                l++;
                int r=ls.query(i,n);
                r--;
                pts.push_back(Point(l,i,ii,ii));
                pts.push_back(Point(l,r+1,ii,-ii));
                pts.push_back(Point(i+1,i,ii,-ii));
                pts.push_back(Point(i+1,r+1,ii,ii));
                ls.update(i,0);
                rs.update(i,0);
            }
        } else{
            int a,b;
            cin >> a >> b;
            b--;
            int k=pts.size();
            pts.push_back(Point(a,b,ii,0));
            pts[k].tind=tind;
            a--;
            if(ls.query(a,b)==n && rs.query(a,b)==-1){
               ex.push_back(ii);
            } else ex.push_back(0);
            if(lls.query(a,b)==n && rrs.query(a,b)==-1){
               ex[tind]++;
            }
            tind++;
        }
    }
    getans();
    for(int i=0;i<tind;i++){
        cout << ans[i]+ex[i] << "\n";
    }
}
signed main(){
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t;
    //cin >> t;
    t=1;
    while(t--) solve();
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20