oj.uz

답안 #858504

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
858504 2023-10-08T15:06:04 Z 8pete8 가로등 (APIO19_street_lamps) C++17
20 / 100
 5000 ms 108116 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
#include<list>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define p push
#define pb push_back
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
#define int long long
const int mxn=3e5,mod=69,lg=42,root=80,inf=1e18;
int n;
bitset<mxn+10>on;
struct seg{
    int vmx[2*mxn+10],vmn[2*mxn+10];
    void init(){for(int i=0;i<=2*mxn;i++)vmx[i]=vmn[i]=0;}
    void updatemx(int pos,int val){
        pos+=n;
        vmx[pos]=val;
        for(;pos>0;pos>>=1)vmx[pos>>1]=max(vmx[pos],vmx[pos^1]);
    }
    int qrymx(int l,int r){
        int ans=0;
        for(l+=n,r+=n;l<=r;l>>=1,r>>=1){
            if(l&1)ans=max(ans,vmx[l++]);
            if(!(r&1))ans=max(ans,vmx[r--]);
        }
        return ans;
    }
    void updatemn(int pos,int val){
        vmn[pos+=n]=val;
        for(;pos>0;pos>>=1)vmn[pos>>1]=min(vmn[pos],vmn[pos^1]);
    }
    int qrymn(int l,int r){
        int ans=inf;
        for(l+=n,r+=n;l<=r;l>>=1,r>>=1){
            if(l&1)ans=min(ans,vmn[l++]);
            if(!(r&1))ans=min(ans,vmn[r--]);
        }
        return ans;
    }
}t;//pos qry mx
struct fen{
    vector<int>all_y[mxn+10],fwk[mxn+10];
    int rank(int x,int y){return upper_bound(all(all_y[x]),y)-all_y[x].begin();}
    void init(vector<pii>v){
        sort(all(v));
        vector<int>cnt_y(mxn+10,0);
        for(auto i:v){
            for(int j=i.f;j<=n;j+=(j&-j))++cnt_y[j];
        }
        for(int i=0;i<=n;i++){
            all_y[i].reserve(cnt_y[i]);
            fwk[i].resize(cnt_y[i]);
        }
        for(auto i:v)for(int j=i.f;j<=n;j+=(j&-j))all_y[j].pb(i.s);
    }
    void update(int x,int y2,int t){
        for(;x<=n;x+=x&-x){
            for (int y=rank(x,y2);y<=all_y[x].size();y+=y&-y)fwk[x][y-1]+=t;
        }
    }
	int qry(int x,int y2){
        int ans=0;
		for (;x;x-=x&-x)for (int y=rank(x,y2);y;y-=y&-y)ans+=fwk[x][y-1];
		return ans;
	}
}f;
pii bs(int pos){
    int l=pos,r=n;
    int a=pos,b=inf;
    while(l<=r){
        int mid=l+(r-l)/2;
        if(t.qrymn(pos,mid)){
            l=mid+1,a=max(a,mid);
        }
        else r=mid-1;
    }
    l=1,r=pos;
    while(l<=r){
        int mid=l+(r-l)/2;
        if(t.qrymn(mid,pos))r=mid-1,b=min(b,mid);
        else l=mid+1;
    }
    return {b,a};
}
vector<int>u;
int32_t main(){
    fastio
    int m;cin>>n>>m;
    string a;cin>>a;
    for(int i=0;i<n;i++){
        if(a[i]=='0')t.updatemx(i+1,inf);
        else on[i+1]=true;
        t.updatemn(i+1,a[i]-'0');
    }
    vector<pii>pass;
    vector<ppii>q;
    q.pb({0,{0,0}});
    for(int i=1;i<=m;i++){
        cin>>a;
        if(a[0]=='t'){
            int x;cin>>x;
            q.pb({1,{x,-1}});
        }
        else{
            int l,r;cin>>l>>r;
            pass.pb({l,r-1});
            q.pb({2,{l,r-1}});
            u.pb(l);
            u.pb(r-1);
        }
    }
    sort(all(u));
    f.init(pass);
    for(int i=1;i<=m;i++){//time
        if(q[i].f==1){
            int x=q[i].s.f;
            if(on[x]){
                on[x]=false;
                pii range=bs(x);
                int g=t.vmx[x+n],comp=0;
                if(g!=inf){
                    comp=i-g-1;
                    auto it=lb(all(u),range.f);
                    if((*it)!=range.f)it++;
                    if(it==u.end())continue;
                    auto it2=ub(all(u),range.s)-1;
                    f.update((*it),(*it2),comp);
                }
                t.updatemn(x,0);
                t.updatemx(x,inf);
            }
            else{
                on[x]=true;
                t.updatemn(x,1);
                t.updatemx(x,i);
            }
        }
        else{
            int l=q[i].s.f,r=q[i].s.s;
            int g=t.qrymx(l,r);
            if(g==inf)g=0;
            else g=i-g;
            cout<<g+f.qry(l,r)<<'\n';
        }
    }
}

Compilation message

street_lamps.cpp: In member function 'void fen::update(long long int, long long int, long long int)':
street_lamps.cpp:81:36: 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]
   81 |             for (int y=rank(x,y2);y<=all_y[x].size();y+=y&-y)fwk[x][y-1]+=t;
      |                                   ~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 19292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 150 ms 46300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 19292 KB Output is correct
2 Correct 5 ms 19288 KB Output is correct
3 Correct 5 ms 19548 KB Output is correct
4 Correct 5 ms 19548 KB Output is correct
5 Correct 80 ms 38268 KB Output is correct
6 Correct 245 ms 58956 KB Output is correct
7 Correct 394 ms 77876 KB Output is correct
8 Correct 581 ms 101664 KB Output is correct
9 Correct 146 ms 52240 KB Output is correct
10 Correct 163 ms 59324 KB Output is correct
11 Correct 170 ms 64452 KB Output is correct
12 Correct 579 ms 108116 KB Output is correct
13 Correct 577 ms 102876 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5034 ms 19544 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 19292 KB Output isn't correct
2 Halted 0 ms 0 KB -