oj.uz

답안 #311087

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
311087 2020-10-09T08:43:42 Z rrrr10000 가로등 (APIO19_street_lamps) C++14
100 / 100
 4614 ms 438308 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||((!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,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:109: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]
  109 |         if(a!=casc[k].size())add(k,a,x);
      |            ~^~~~~~~~~~~~~~~~
street_lamps.cpp:110: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]
  110 |         if(b!=casc[k].size())add(k,b,-x);
      |            ~^~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1890 ms 209912 KB Output is correct
2 Correct 2164 ms 210132 KB Output is correct
3 Correct 2130 ms 210048 KB Output is correct
4 Correct 2276 ms 217196 KB Output is correct
5 Correct 2372 ms 215912 KB Output is correct
6 Correct 1514 ms 111764 KB Output is correct
7 Correct 4173 ms 438308 KB Output is correct
8 Correct 3665 ms 425716 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 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 538 ms 19332 KB Output is correct
6 Correct 1495 ms 113868 KB Output is correct
7 Correct 2548 ms 214500 KB Output is correct
8 Correct 4016 ms 424576 KB Output is correct
9 Correct 1645 ms 208704 KB Output is correct
10 Correct 2345 ms 423356 KB Output is correct
11 Correct 2146 ms 423484 KB Output is correct
12 Correct 4352 ms 437652 KB Output is correct
13 Correct 4019 ms 424512 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 896 KB Output is correct
2 Correct 3 ms 928 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 4364 ms 430296 KB Output is correct
6 Correct 2816 ms 216016 KB Output is correct
7 Correct 1756 ms 110956 KB Output is correct
8 Correct 471 ms 12428 KB Output is correct
9 Correct 1309 ms 103904 KB Output is correct
10 Correct 324 ms 7476 KB Output is correct
11 Correct 1371 ms 103776 KB Output is correct
12 Correct 325 ms 7476 KB Output is correct
13 Correct 1440 ms 103776 KB Output is correct
14 Correct 340 ms 7476 KB Output is correct
15 Correct 4614 ms 437220 KB Output is correct
16 Correct 4103 ms 424456 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 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 1890 ms 209912 KB Output is correct
9 Correct 2164 ms 210132 KB Output is correct
10 Correct 2130 ms 210048 KB Output is correct
11 Correct 2276 ms 217196 KB Output is correct
12 Correct 2372 ms 215912 KB Output is correct
13 Correct 1514 ms 111764 KB Output is correct
14 Correct 4173 ms 438308 KB Output is correct
15 Correct 3665 ms 425716 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 538 ms 19332 KB Output is correct
21 Correct 1495 ms 113868 KB Output is correct
22 Correct 2548 ms 214500 KB Output is correct
23 Correct 4016 ms 424576 KB Output is correct
24 Correct 1645 ms 208704 KB Output is correct
25 Correct 2345 ms 423356 KB Output is correct
26 Correct 2146 ms 423484 KB Output is correct
27 Correct 4352 ms 437652 KB Output is correct
28 Correct 4019 ms 424512 KB Output is correct
29 Correct 3 ms 896 KB Output is correct
30 Correct 3 ms 928 KB Output is correct
31 Correct 2 ms 640 KB Output is correct
32 Correct 1 ms 384 KB Output is correct
33 Correct 4364 ms 430296 KB Output is correct
34 Correct 2816 ms 216016 KB Output is correct
35 Correct 1756 ms 110956 KB Output is correct
36 Correct 471 ms 12428 KB Output is correct
37 Correct 1309 ms 103904 KB Output is correct
38 Correct 324 ms 7476 KB Output is correct
39 Correct 1371 ms 103776 KB Output is correct
40 Correct 325 ms 7476 KB Output is correct
41 Correct 1440 ms 103776 KB Output is correct
42 Correct 340 ms 7476 KB Output is correct
43 Correct 4614 ms 437220 KB Output is correct
44 Correct 4103 ms 424456 KB Output is correct
45 Correct 990 ms 103368 KB Output is correct
46 Correct 1450 ms 103028 KB Output is correct
47 Correct 1524 ms 105308 KB Output is correct
48 Correct 2499 ms 216056 KB Output is correct
49 Correct 2830 ms 423228 KB Output is correct
50 Correct 2859 ms 423152 KB Output is correct
51 Correct 2522 ms 423188 KB Output is correct
52 Correct 2091 ms 422892 KB Output is correct
53 Correct 2108 ms 422836 KB Output is correct
54 Correct 2035 ms 422836 KB Output is correct