oj.uz

Submission #311085

# Submission time Handle Problem Language Result Execution time Memory
311085 2020-10-09T08:38:51 Z rrrr10000 Street Lamps (APIO19_street_lamps) C++14
100 / 100
 4192 ms 438872 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;
vi NN;
ll N;
void initseg(){
    NN=vi(N*2-1,1);
    rep(t,N*2-1){
        while(NN[t]<casc[t].size())NN[t]<<=1;
        seg.pb(vi(NN[t]*2-1));
    }
}
void add(ll t,ll i,ll x){
    i=NN[t]+i-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);
    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){
            bool A=(a==casc[i*2+1].size()),B=(b==casc[i*2+2].size());
            if(A&&B)break;
            if(A)casc[i].pb(casc[i*2+2][b++]);
            else if(B)casc[i].pb(casc[i*2+1][a++]);
            else if(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,NN[x.fi]);
    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){
        ll a=lb(casc[k],P(y1,-inf)),b=lb(casc[k],P(y2,inf));  //[a,b)+=x
        if(a!=casc[k].size())add(k,a,x);
        if(b!=casc[k].size())add(k,b,-x);
        return;
    }
    add_all(x1,x2,y1,y2,k*2+1,l,(l+r)/2,x);
    add_all(x1,x2,y1,y2,k*2+2,(l+r)/2,r,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,0,0,N,-(i+1));
            else add_all(a,ID,ID,b,0,0,N,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 initseg()':
street_lamps.cpp:63:20: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         while(NN[t]<casc[t].size())NN[t]<<=1;
street_lamps.cpp: In function 'void init_fractional_cascading()':
street_lamps.cpp:85: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]
   85 |     while(N<points.size())N<<=1;
      |           ~^~~~~~~~~~~~~~
street_lamps.cpp:86: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]
   86 |     while(points.size()<N)points.pb(0,0,points.size());sort(all(points));
      |           ~~~~~~~~~~~~~^~
street_lamps.cpp:86:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   86 |     while(points.size()<N)points.pb(0,0,points.size());sort(all(points));
      |     ^~~~~
street_lamps.cpp:86:56: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   86 |     while(points.size()<N)points.pb(0,0,points.size());sort(all(points));
      |                                                        ^~~~
street_lamps.cpp:92: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]
   92 |             bool A=(a==casc[i*2+1].size()),B=(b==casc[i*2+2].size());
      |                     ~^~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:92: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]
   92 |             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:111:13: 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]
  111 |         if(a!=casc[k].size())add(k,a,x);
      |            ~^~~~~~~~~~~~~~~~
street_lamps.cpp:112:13: 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]
  112 |         if(b!=casc[k].size())add(k,b,-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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1802 ms 210100 KB Output is correct
2 Correct 2189 ms 210160 KB Output is correct
3 Correct 2198 ms 210160 KB Output is correct
4 Correct 2239 ms 217176 KB Output is correct
5 Correct 2438 ms 215972 KB Output is correct
6 Correct 1508 ms 111916 KB Output is correct
7 Correct 4189 ms 438872 KB Output is correct
8 Correct 3777 ms 425776 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 3 ms 896 KB Output is correct
5 Correct 555 ms 19212 KB Output is correct
6 Correct 1552 ms 113884 KB Output is correct
7 Correct 2548 ms 214644 KB Output is correct
8 Correct 3921 ms 424448 KB Output is correct
9 Correct 1647 ms 208684 KB Output is correct
10 Correct 2397 ms 423384 KB Output is correct
11 Correct 2164 ms 423448 KB Output is correct
12 Correct 4155 ms 437420 KB Output is correct
13 Correct 3833 ms 424532 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 896 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 4002 ms 430352 KB Output is correct
6 Correct 2579 ms 216036 KB Output is correct
7 Correct 1508 ms 111156 KB Output is correct
8 Correct 436 ms 12432 KB Output is correct
9 Correct 1214 ms 103656 KB Output is correct
10 Correct 321 ms 7476 KB Output is correct
11 Correct 1232 ms 103884 KB Output is correct
12 Correct 321 ms 7476 KB Output is correct
13 Correct 1208 ms 103708 KB Output is correct
14 Correct 321 ms 7476 KB Output is correct
15 Correct 4192 ms 437324 KB Output is correct
16 Correct 3780 ms 424780 KB Output is correct

Subtask #5
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
8 Correct 1802 ms 210100 KB Output is correct
9 Correct 2189 ms 210160 KB Output is correct
10 Correct 2198 ms 210160 KB Output is correct
11 Correct 2239 ms 217176 KB Output is correct
12 Correct 2438 ms 215972 KB Output is correct
13 Correct 1508 ms 111916 KB Output is correct
14 Correct 4189 ms 438872 KB Output is correct
15 Correct 3777 ms 425776 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 2 ms 640 KB Output is correct
18 Correct 3 ms 896 KB Output is correct
19 Correct 3 ms 896 KB Output is correct
20 Correct 555 ms 19212 KB Output is correct
21 Correct 1552 ms 113884 KB Output is correct
22 Correct 2548 ms 214644 KB Output is correct
23 Correct 3921 ms 424448 KB Output is correct
24 Correct 1647 ms 208684 KB Output is correct
25 Correct 2397 ms 423384 KB Output is correct
26 Correct 2164 ms 423448 KB Output is correct
27 Correct 4155 ms 437420 KB Output is correct
28 Correct 3833 ms 424532 KB Output is correct
29 Correct 3 ms 896 KB Output is correct
30 Correct 3 ms 896 KB Output is correct
31 Correct 2 ms 640 KB Output is correct
32 Correct 1 ms 384 KB Output is correct
33 Correct 4002 ms 430352 KB Output is correct
34 Correct 2579 ms 216036 KB Output is correct
35 Correct 1508 ms 111156 KB Output is correct
36 Correct 436 ms 12432 KB Output is correct
37 Correct 1214 ms 103656 KB Output is correct
38 Correct 321 ms 7476 KB Output is correct
39 Correct 1232 ms 103884 KB Output is correct
40 Correct 321 ms 7476 KB Output is correct
41 Correct 1208 ms 103708 KB Output is correct
42 Correct 321 ms 7476 KB Output is correct
43 Correct 4192 ms 437324 KB Output is correct
44 Correct 3780 ms 424780 KB Output is correct
45 Correct 864 ms 103432 KB Output is correct
46 Correct 1182 ms 103096 KB Output is correct
47 Correct 1176 ms 105504 KB Output is correct
48 Correct 2157 ms 216080 KB Output is correct
49 Correct 2472 ms 423520 KB Output is correct
50 Correct 2477 ms 423436 KB Output is correct
51 Correct 2317 ms 423392 KB Output is correct
52 Correct 1854 ms 423148 KB Output is correct
53 Correct 1884 ms 423220 KB Output is correct
54 Correct 1838 ms 422964 KB Output is correct