Submission #1381620


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

// 区間add, 区間min
struct LazySegTree{
    int n; vector<ll> dat,lazy;
    //初期化
    LazySegTree(int _n){
        n=1;
        while(n<_n) n*=2;
        dat=vector<ll>(2*n-1,0);
        lazy=vector<ll>(2*n-1,0);
    }

    void setLazy(int k, ll v){
        lazy[k] += v;
        dat[k] += v;
    }

    void push(int k, int l, int r){
        if(lazy[k]!=0){
            setLazy(2*k+1,lazy[k]);
            setLazy(2*k+2,lazy[k]);
        }
        lazy[k]=0;
    }

    void fix(int k, int l, int r){
        dat[k]=max(dat[2*k+1],dat[2*k+2]);
    }

    ll merge(ll x, ll y){
        return max(x,y);
    }

    //内部的に投げられるクエリ
    void _add(int a, int b, ll x, int k, int l, int r){
        if(r<=a || b<=l) return;
        if(a<=l && r<=b){
            setLazy(k,x);
            return;
        }

        push(k,l,r);
        _add(a,b,x,2*k+1,l,(l+r)/2);
        _add(a,b,x,2*k+2,(l+r)/2,r);

        fix(k,l,r);
    }
    //[a,b)に+x
    void add(int a, int b, ll x){
        return _add(a,b,x,0,0,n);
    }

    //内部的に投げられるクエリ
    ll _query(int a, int b, int k, int l, int r){
        if(r<=a || b<=l) return LLONG_MIN/2;
        if(a<=l && r<=b) return dat[k];

        push(k,l,r);
        ll vl=_query(a,b,2*k+1,l,(l+r)/2);
        ll vr=_query(a,b,2*k+2,(l+r)/2,r);
        return merge(vl,vr);
    }
    //[a,b)
    ll query(int a, int b){
        return _query(a,b,0,0,n);
    }
};

ll f(string t, char c)
{
    string x=t;
    reverse(all(x));
    while(x.size()<10) x+=c;
    return atoll(x.c_str());
}

int main()
{
    int n;
    cin >>n;

    vector<string> a(n);
    vector<ll> b(n);
    rep(i,n) cin >>a[i] >>b[i];

    vector<ll> l(n),r(n);
    vector<ll> v;
    rep(i,n)
    {
        l[i] = f(a[i],'0');
        r[i] = f(a[i],'9');
        v.pb(l[i]);
        v.pb(r[i]);
    }

    sort(all(v));
    v.erase(unique(all(v)),v.end());
    int V = v.size();

    LazySegTree st(V);
    rep(i,n)
    {
        int lidx = lower_bound(all(v),l[i])-v.begin();
        int ridx = lower_bound(all(v),r[i])-v.begin();
        st.add(lidx,ridx+1,b[i]);
        cout << st.query(0,V) << endl;
    }

    return 0;
}

Submission Info

Submission Time
Task E - 宝くじ
User imulan
Language C++14 (GCC 5.4.1)
Score 200
Code Size 2799 Byte
Status AC
Exec Time 403 ms
Memory 20468 KB

Judge Result

Set Name All
Score / Max Score 200 / 200
Status
AC × 25
Set Name Test Cases
All scrambled_00.txt, scrambled_01.txt, scrambled_02.txt, scrambled_03.txt, scrambled_04.txt, scrambled_05.txt, scrambled_06.txt, scrambled_07.txt, scrambled_08.txt, scrambled_09.txt, scrambled_10.txt, scrambled_11.txt, scrambled_12.txt, scrambled_13.txt, scrambled_14.txt, scrambled_15.txt, scrambled_16.txt, scrambled_17.txt, scrambled_18.txt, scrambled_19.txt, scrambled_20.txt, scrambled_21.txt, scrambled_22.txt, scrambled_23.txt, scrambled_24.txt
Case Name Status Exec Time Memory
scrambled_00.txt AC 1 ms 256 KB
scrambled_01.txt AC 1 ms 256 KB
scrambled_02.txt AC 300 ms 12788 KB
scrambled_03.txt AC 263 ms 11248 KB
scrambled_04.txt AC 304 ms 12788 KB
scrambled_05.txt AC 207 ms 8308 KB
scrambled_06.txt AC 243 ms 9716 KB
scrambled_07.txt AC 77 ms 3324 KB
scrambled_08.txt AC 129 ms 5492 KB
scrambled_09.txt AC 317 ms 11376 KB
scrambled_10.txt AC 265 ms 9716 KB
scrambled_11.txt AC 85 ms 3320 KB
scrambled_12.txt AC 255 ms 9332 KB
scrambled_13.txt AC 62 ms 2432 KB
scrambled_14.txt AC 374 ms 15984 KB
scrambled_15.txt AC 16 ms 896 KB
scrambled_16.txt AC 357 ms 15600 KB
scrambled_17.txt AC 53 ms 2556 KB
scrambled_18.txt AC 344 ms 14964 KB
scrambled_19.txt AC 403 ms 20468 KB
scrambled_20.txt AC 400 ms 20464 KB
scrambled_21.txt AC 248 ms 11892 KB
scrambled_22.txt AC 246 ms 11892 KB
scrambled_23.txt AC 51 ms 2940 KB
scrambled_24.txt AC 107 ms 5752 KB