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 |
|
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 |