oj.uz

Submission #311092

# Submission time Handle Problem Language Result Execution time Memory
311092 2020-10-09T08:51:13 Z rrrr10000 Street Lamps (APIO19_street_lamps) C++14
100 / 100
 4232 ms 435672 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;
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()+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||((!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){
        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 init_fractional_cascading()':
street_lamps.cpp:80: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]
   80 |     while(N<points.size())N<<=1;
      |           ~^~~~~~~~~~~~~~
street_lamps.cpp:81: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]
   81 |     while(points.size()<N)points.pb(0,0,points.size());sort(all(points));
      |           ~~~~~~~~~~~~~^~
street_lamps.cpp:81:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   81 |     while(points.size()<N)points.pb(0,0,points.size());sort(all(points));
      |     ^~~~~
street_lamps.cpp:81:56: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   81 |     while(points.size()<N)points.pb(0,0,points.size());sort(all(points));
      |                                                        ^~~~
street_lamps.cpp:87: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]
   87 |             bool A=(a==casc[i*2+1].size()),B=(b==casc[i*2+2].size());
      |                     ~^~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:87: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]
   87 |             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:104: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]
  104 |         if(a!=casc[k].size())add(k,a,x);
      |            ~^~~~~~~~~~~~~~~~
street_lamps.cpp:105: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]
  105 |         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 392 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 3 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2231 ms 207996 KB Output is correct
2 Correct 2391 ms 208288 KB Output is correct
3 Correct 2398 ms 208744 KB Output is correct
4 Correct 2364 ms 215908 KB Output is correct
5 Correct 2524 ms 214588 KB Output is correct
6 Correct 1589 ms 111560 KB Output is correct
7 Correct 4220 ms 435672 KB Output is correct
8 Correct 3812 ms 422484 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 559 ms 20108 KB Output is correct
6 Correct 1524 ms 113780 KB Output is correct
7 Correct 2593 ms 213228 KB Output is correct
8 Correct 3971 ms 421544 KB Output is correct
9 Correct 1588 ms 207512 KB Output is correct
10 Correct 2312 ms 420020 KB Output is correct
11 Correct 2168 ms 420020 KB Output is correct
12 Correct 4232 ms 433868 KB Output is correct
13 Correct 3818 ms 421200 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 912 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 4107 ms 426908 KB Output is correct
6 Correct 2620 ms 214764 KB Output is correct
7 Correct 1481 ms 110712 KB Output is correct
8 Correct 441 ms 13068 KB Output is correct
9 Correct 1211 ms 103496 KB Output is correct
10 Correct 330 ms 8116 KB Output is correct
11 Correct 1201 ms 103520 KB Output is correct
12 Correct 332 ms 8340 KB Output is correct
13 Correct 1210 ms 103616 KB Output is correct
14 Correct 324 ms 8116 KB Output is correct
15 Correct 4180 ms 433936 KB Output is correct
16 Correct 3789 ms 421212 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 392 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 3 ms 384 KB Output is correct
8 Correct 2231 ms 207996 KB Output is correct
9 Correct 2391 ms 208288 KB Output is correct
10 Correct 2398 ms 208744 KB Output is correct
11 Correct 2364 ms 215908 KB Output is correct
12 Correct 2524 ms 214588 KB Output is correct
13 Correct 1589 ms 111560 KB Output is correct
14 Correct 4220 ms 435672 KB Output is correct
15 Correct 3812 ms 422484 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 559 ms 20108 KB Output is correct
21 Correct 1524 ms 113780 KB Output is correct
22 Correct 2593 ms 213228 KB Output is correct
23 Correct 3971 ms 421544 KB Output is correct
24 Correct 1588 ms 207512 KB Output is correct
25 Correct 2312 ms 420020 KB Output is correct
26 Correct 2168 ms 420020 KB Output is correct
27 Correct 4232 ms 433868 KB Output is correct
28 Correct 3818 ms 421200 KB Output is correct
29 Correct 3 ms 896 KB Output is correct
30 Correct 3 ms 912 KB Output is correct
31 Correct 3 ms 640 KB Output is correct
32 Correct 1 ms 384 KB Output is correct
33 Correct 4107 ms 426908 KB Output is correct
34 Correct 2620 ms 214764 KB Output is correct
35 Correct 1481 ms 110712 KB Output is correct
36 Correct 441 ms 13068 KB Output is correct
37 Correct 1211 ms 103496 KB Output is correct
38 Correct 330 ms 8116 KB Output is correct
39 Correct 1201 ms 103520 KB Output is correct
40 Correct 332 ms 8340 KB Output is correct
41 Correct 1210 ms 103616 KB Output is correct
42 Correct 324 ms 8116 KB Output is correct
43 Correct 4180 ms 433936 KB Output is correct
44 Correct 3789 ms 421212 KB Output is correct
45 Correct 868 ms 103176 KB Output is correct
46 Correct 1155 ms 102752 KB Output is correct
47 Correct 1164 ms 104992 KB Output is correct
48 Correct 2175 ms 214756 KB Output is correct
49 Correct 2449 ms 420148 KB Output is correct
50 Correct 2514 ms 419964 KB Output is correct
51 Correct 2325 ms 419552 KB Output is correct
52 Correct 1848 ms 418740 KB Output is correct
53 Correct 1853 ms 418736 KB Output is correct
54 Correct 1857 ms 418868 KB Output is correct