oj.uz

Submission #311106

# Submission time Handle Problem Language Result Execution time Memory
311106 2020-10-09T09:13:54 Z rrrr10000 Street Lamps (APIO19_street_lamps) C++14
20 / 100
 3035 ms 524292 KB 
#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
typedef int ll;
typedef pair<int,int> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
typedef multiset<ll> S;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vvvvi=vector<vvvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
const ll INF=1001001001;
const ll mod=1000000007;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void noyes(T b){if(b)out("no");else out("yes");}
template<class T> void NoYes(T b){if(b)out("No");else out("Yes");}
template<class T> void NOYES(T b){if(b)out("NO");else out("YES");}
void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
vvp casc,id;
vvi seg;
vvi L,R;
ll N;
void initseg(){
    rep(t,N*2-1)seg.pb(vi(casc[t].size()*2-1));
}
void add(ll t,ll i,ll x){
    i+=casc[t].size()-1;
    seg[t][i]+=x;
    while(i>0){
        i=(i-1)/2;
        seg[t][i]=seg[t][i*2+1]+seg[t][i*2+2];
    }
}
ll getsum(ll t,ll a,ll b,ll k,ll l,ll r){
    if(r<=a||b<=l)return 0;
    if(a<=l&&r<=b)return seg[t][k];
    ll c1=getsum(t,a,b,k*2+1,l,(l+r)/2);
    ll c2=getsum(t,a,b,k*2+2,(l+r)/2,r);
    return c1+c2;
}
vector<PP> points;
void init_fractional_cascading(){  //(x座標,y座標,id)
    N=1;
    while(N<points.size())N<<=1;
    while(points.size()<N)points.pb(0,0,points.size());sort(all(points));
    casc=vvp(2*N-1);id=vvp(N);L=vvi(2*N-1);R=vvi(2*N-1);
    rep(i,N)casc[i+N-1].pb(get<1>(points[i]),get<2>(points[i]));
    for(int i=N-2;i>=0;i--){
        ll a=0,b=0;
        while(true){
            L[i].pb(a);R[i].pb(b);
            bool A=(a==casc[i*2+1].size()),B=(b==casc[i*2+2].size());
            if(A&&B)break;
            if(A||((!B)&&casc[i*2+1][a]>casc[i*2+2][b]))casc[i].pb(casc[i*2+2][b++]);
            else casc[i].pb(casc[i*2+1][a++]);
        }
    }
    rep(i,2*N-1)rep(j,casc[i].size())id[casc[i][j].se].pb(i,j);
}
ll answer_query(int i){
    ll res=0;
    for(auto x:id[i])res+=getsum(x.fi,0,x.se+1,0,0,casc[x.fi].size());
    return res;
}
void add_all(int x1,int x2,int y1,int y2,int k,int l,int r,ll X){//[x1,x2],[y1,y2],[l,r)
    if(x2<get<0>(points[l])||get<0>(points[r-1])<x1)return;
    if(x1<=get<0>(points[l])&&get<0>(points[r-1])<=x2){
        if(y1!=casc[k].size())add(k,y1,X);
        if(y2!=casc[k].size())add(k,y2,-X);
        return;
    }
    add_all(x1,x2,L[k][y1],L[k][y2],k*2+1,l,(l+r)/2,X);
    add_all(x1,x2,R[k][y1],R[k][y2],k*2+2,(l+r)/2,r,X);
}
void add_all(ll x1,ll x2,ll y1,ll y2,ll X){
    y1=lb(casc[0],P(y1,0));
    y2=lb(casc[0],P(y2+1,0));
    add_all(x1,x2,y1,y2,0,0,N,X);
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,q;cin>>n>>q;
    string str;cin>>str;
    vp query(q);
    ll cnt=0;
    rep(i,q){
        string t;cin>>t;
        if(t=="query"){
            ll a,b;cin>>a>>b;
            query[i]=P(a-1,b-2);
            points.pb(a-1,b-2,cnt++);
        }
        else{
            ll a;cin>>a;
            query[i]=P(-1,a-1);
        }
    }
    init_fractional_cascading();
    initseg();
    set<ll> S;rep(i,n)if(str[i]=='0')S.insert(i);
    cnt=0;
    rep(i,q){
        if(query[i].fi==-1){
            ll ID=query[i].se;
            if(str[ID]=='0')S.erase(ID);
            auto itr=S.lower_bound(ID);
            ll a=0,b=n-1;
            if(itr!=S.begin()){
                itr--;a=(*itr)+1;itr++;
            }
            if(itr!=S.end())b=(*itr)-1;
            if(str[ID]=='0')add_all(a,ID,ID,b,-(i+1));
            else add_all(a,ID,ID,b,i+1);
            if(str[ID]=='1')S.insert(ID);
            str[ID]='1'+'0'-str[ID];
        }
        else{
            ll res=answer_query(cnt++);
            auto itr=S.lower_bound(query[i].fi);
            if(itr==S.end()||*itr>query[i].se)res+=i+1;
            out(res);
        }
    }
}

Compilation message

street_lamps.cpp:34:14: warning: overflow in conversion from 'long int' to 'll' {aka 'int'} changes value from '1001001001001001001' to '1551474729' [-Woverflow]
   34 | const ll inf=1001001001001001001;
      |              ^~~~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'void init_fractional_cascading()':
street_lamps.cpp:81:12: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     while(N<points.size())N<<=1;
      |           ~^~~~~~~~~~~~~~
street_lamps.cpp:82:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   82 |     while(points.size()<N)points.pb(0,0,points.size());sort(all(points));
      |           ~~~~~~~~~~~~~^~
street_lamps.cpp:82:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   82 |     while(points.size()<N)points.pb(0,0,points.size());sort(all(points));
      |     ^~~~~
street_lamps.cpp:82:56: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   82 |     while(points.size()<N)points.pb(0,0,points.size());sort(all(points));
      |                                                        ^~~~
street_lamps.cpp:89:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |             bool A=(a==casc[i*2+1].size()),B=(b==casc[i*2+2].size());
      |                     ~^~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:89:48: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |             bool A=(a==casc[i*2+1].size()),B=(b==casc[i*2+2].size());
      |                                               ~^~~~~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'void add_all(int, int, int, int, int, int, int, ll)':
street_lamps.cpp:105:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         if(y1!=casc[k].size())add(k,y1,X);
      |            ~~^~~~~~~~~~~~~~~~
street_lamps.cpp:106:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         if(y2!=casc[k].size())add(k,y2,-X);
      |            ~~^~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2181 ms 307800 KB Output is correct
2 Correct 2619 ms 308132 KB Output is correct
3 Correct 2745 ms 307792 KB Output is correct
4 Correct 2846 ms 314876 KB Output is correct
5 Correct 2947 ms 313624 KB Output is correct
6 Correct 2087 ms 159220 KB Output is correct
7 Runtime error 1708 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 4 ms 1152 KB Output is correct
4 Correct 3 ms 1152 KB Output is correct
5 Correct 659 ms 20752 KB Output is correct
6 Correct 2004 ms 161136 KB Output is correct
7 Correct 3035 ms 312424 KB Output is correct
8 Runtime error 1861 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1152 KB Output is correct
2 Correct 4 ms 1152 KB Output is correct
3 Correct 3 ms 768 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Runtime error 1864 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 2181 ms 307800 KB Output is correct
9 Correct 2619 ms 308132 KB Output is correct
10 Correct 2745 ms 307792 KB Output is correct
11 Correct 2846 ms 314876 KB Output is correct
12 Correct 2947 ms 313624 KB Output is correct
13 Correct 2087 ms 159220 KB Output is correct
14 Runtime error 1708 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -