oj.uz

Submission #441177

# Submission time Handle Problem Language Result Execution time Memory
441177 2021-07-04T13:21:19 Z leaked Money (IZhO17_money) C++14
45 / 100
 1500 ms 77380 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//    #pragma GCC optimize("-O3")
//    #pragma GCC optimize("no-stack-protector")
//    #pragma GCC optimize("fast-math")
//    #pragma GCC optimize("Ofast")
//    #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//    #pragma GCC target("avx,avx2,fma")
//    #pragma GCC optimization ("unroll-loops")
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
//using namespace __gnu_pbds;
#define fast_io ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define vec vector
#define getin freopen("input.txt","r",stdin);
#define getout ofstream cout("output.txt");
#define getfiles getin;getout
#define m_p make_pair
#define f first
#define sz(x) (int)x.size()
#define pw(x) (1LL<<x)
#define pb push_back
#define endl '\n'
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define s second
typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef long double ld;
template<typename T>bool umax(T &a,const T &b)  {return (a<b?a=b,1:0);}
template<typename T>bool umin(T &a,const T &b)  {return (a>b?a=b,1:0);}
const int lg=20;
const int N=1e6+1;
int a[N];
int n;
int uk[N];
deque<pii>dq1,dq2;
void add1(pii v){
    while(sz(dq1) && dq1.back().f<v.f){
        dq1.pop_back();
    }
    dq1.push_back(v);
}
void era1(pii v){
    assert(sz(dq1));
    if(dq1.front()==v)
        dq1.pop_front();
}
void add2(pii v){
    while(sz(dq2) && dq2.back().f>v.f){
        dq2.pop_back();
    }
    dq2.push_back(v);
}
void era2(pii v){
    assert(sz(dq2));
    if(dq2.front()==v)
        dq2.pop_front();
}
int t[4*N];
void upd(int id,int x,int v,int tl,int tr){
    if(tl==tr){
        t[v]=x;
        return;
    }
    int tm=(tl+tr)>>1;
    if(tm>=id)
        upd(id,x,2*v,tl,tm);
    else
        upd(id,x,2*v+1,tm+1,tr);
    t[v]=min(t[2*v],t[2*v+1]);
}
int get(int l,int r,int v,int tl,int tr){
    if(tl>=l && tr<=r){
        return t[v];
    }
    if(tl>r || tr<l){
        return 2e9;
    }
    int tm=(tl+tr)>>1;
    return min(get(l,r,2*v,tl,tm),get(l,r,2*v+1,tm+1,tr));
}
signed main(){

    fast_io;
//    ifstream cin("money.in");
//    ofstream cout("money.out");
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    int l=0;
    set<int>st;
    auto ok=[&](){
        int x=dq2.front().f,y=dq1.front().f;
//        debug()<<imie(x)imie(y)imie(l);
        auto it=st.upper_bound(x);
        if(it!=st.end() && *it<y){
            return 0;
        }
        return 1;
    };
    for(int i=0;i<n;i++){
        add1({a[i],i});
        add2({a[i],i});
        while(!ok() || a[i]!=dq1.front().f){
            era1({a[l],l});
            era2({a[l],l});
            st.insert(a[l]);
            l++;
        }
        uk[i]=l;
    }
    fill(t,t+4*N,2e9);
    upd(0,0,1,0,n);
    for(int i=0;i<n;i++){
        int vl=get(uk[i],n,1,0,n);
//        debug()<<imie(uk[i]);
        upd(i+1,vl+1,1,0,n);
    }
    cout<<get(n,n,1,0,n);
    return 0;
}
/*
1
4 2
0110

*/

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15952 KB Output is correct
2 Correct 9 ms 15948 KB Output is correct
3 Correct 9 ms 15948 KB Output is correct
4 Correct 9 ms 15976 KB Output is correct
5 Correct 9 ms 15924 KB Output is correct
6 Correct 9 ms 15948 KB Output is correct
7 Correct 9 ms 15948 KB Output is correct
8 Correct 9 ms 15948 KB Output is correct
9 Correct 9 ms 15948 KB Output is correct
10 Correct 9 ms 15948 KB Output is correct
11 Correct 10 ms 15944 KB Output is correct
12 Correct 9 ms 15912 KB Output is correct
13 Correct 15 ms 15948 KB Output is correct
14 Correct 11 ms 15992 KB Output is correct
15 Correct 9 ms 15952 KB Output is correct
16 Correct 9 ms 15948 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15952 KB Output is correct
2 Correct 9 ms 15948 KB Output is correct
3 Correct 9 ms 15948 KB Output is correct
4 Correct 9 ms 15976 KB Output is correct
5 Correct 9 ms 15924 KB Output is correct
6 Correct 9 ms 15948 KB Output is correct
7 Correct 9 ms 15948 KB Output is correct
8 Correct 9 ms 15948 KB Output is correct
9 Correct 9 ms 15948 KB Output is correct
10 Correct 9 ms 15948 KB Output is correct
11 Correct 10 ms 15944 KB Output is correct
12 Correct 9 ms 15912 KB Output is correct
13 Correct 15 ms 15948 KB Output is correct
14 Correct 11 ms 15992 KB Output is correct
15 Correct 9 ms 15952 KB Output is correct
16 Correct 9 ms 15948 KB Output is correct
17 Correct 9 ms 15948 KB Output is correct
18 Correct 11 ms 15948 KB Output is correct
19 Correct 11 ms 15964 KB Output is correct
20 Correct 11 ms 15948 KB Output is correct
21 Correct 10 ms 15964 KB Output is correct
22 Correct 10 ms 15948 KB Output is correct
23 Correct 9 ms 15948 KB Output is correct
24 Correct 9 ms 15964 KB Output is correct
25 Correct 10 ms 15948 KB Output is correct
26 Correct 10 ms 15948 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15952 KB Output is correct
2 Correct 9 ms 15948 KB Output is correct
3 Correct 9 ms 15948 KB Output is correct
4 Correct 9 ms 15976 KB Output is correct
5 Correct 9 ms 15924 KB Output is correct
6 Correct 9 ms 15948 KB Output is correct
7 Correct 9 ms 15948 KB Output is correct
8 Correct 9 ms 15948 KB Output is correct
9 Correct 9 ms 15948 KB Output is correct
10 Correct 9 ms 15948 KB Output is correct
11 Correct 10 ms 15944 KB Output is correct
12 Correct 9 ms 15912 KB Output is correct
13 Correct 15 ms 15948 KB Output is correct
14 Correct 11 ms 15992 KB Output is correct
15 Correct 9 ms 15952 KB Output is correct
16 Correct 9 ms 15948 KB Output is correct
17 Correct 9 ms 15948 KB Output is correct
18 Correct 11 ms 15948 KB Output is correct
19 Correct 11 ms 15964 KB Output is correct
20 Correct 11 ms 15948 KB Output is correct
21 Correct 10 ms 15964 KB Output is correct
22 Correct 10 ms 15948 KB Output is correct
23 Correct 9 ms 15948 KB Output is correct
24 Correct 9 ms 15964 KB Output is correct
25 Correct 10 ms 15948 KB Output is correct
26 Correct 10 ms 15948 KB Output is correct
27 Correct 9 ms 15948 KB Output is correct
28 Correct 9 ms 15948 KB Output is correct
29 Correct 10 ms 15948 KB Output is correct
30 Correct 14 ms 15948 KB Output is correct
31 Correct 9 ms 15948 KB Output is correct
32 Correct 14 ms 15948 KB Output is correct
33 Correct 10 ms 15960 KB Output is correct
34 Correct 9 ms 15948 KB Output is correct
35 Correct 9 ms 15948 KB Output is correct
36 Correct 9 ms 15948 KB Output is correct
37 Correct 9 ms 15948 KB Output is correct
38 Correct 11 ms 15948 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15952 KB Output is correct
2 Correct 9 ms 15948 KB Output is correct
3 Correct 9 ms 15948 KB Output is correct
4 Correct 9 ms 15976 KB Output is correct
5 Correct 9 ms 15924 KB Output is correct
6 Correct 9 ms 15948 KB Output is correct
7 Correct 9 ms 15948 KB Output is correct
8 Correct 9 ms 15948 KB Output is correct
9 Correct 9 ms 15948 KB Output is correct
10 Correct 9 ms 15948 KB Output is correct
11 Correct 10 ms 15944 KB Output is correct
12 Correct 9 ms 15912 KB Output is correct
13 Correct 15 ms 15948 KB Output is correct
14 Correct 11 ms 15992 KB Output is correct
15 Correct 9 ms 15952 KB Output is correct
16 Correct 9 ms 15948 KB Output is correct
17 Correct 9 ms 15948 KB Output is correct
18 Correct 11 ms 15948 KB Output is correct
19 Correct 11 ms 15964 KB Output is correct
20 Correct 11 ms 15948 KB Output is correct
21 Correct 10 ms 15964 KB Output is correct
22 Correct 10 ms 15948 KB Output is correct
23 Correct 9 ms 15948 KB Output is correct
24 Correct 9 ms 15964 KB Output is correct
25 Correct 10 ms 15948 KB Output is correct
26 Correct 10 ms 15948 KB Output is correct
27 Correct 9 ms 15948 KB Output is correct
28 Correct 9 ms 15948 KB Output is correct
29 Correct 10 ms 15948 KB Output is correct
30 Correct 14 ms 15948 KB Output is correct
31 Correct 9 ms 15948 KB Output is correct
32 Correct 14 ms 15948 KB Output is correct
33 Correct 10 ms 15960 KB Output is correct
34 Correct 9 ms 15948 KB Output is correct
35 Correct 9 ms 15948 KB Output is correct
36 Correct 9 ms 15948 KB Output is correct
37 Correct 9 ms 15948 KB Output is correct
38 Correct 11 ms 15948 KB Output is correct
39 Correct 359 ms 22932 KB Output is correct
40 Correct 501 ms 27588 KB Output is correct
41 Correct 221 ms 21592 KB Output is correct
42 Correct 198 ms 20980 KB Output is correct
43 Correct 139 ms 19524 KB Output is correct
44 Correct 638 ms 30644 KB Output is correct
45 Correct 582 ms 30480 KB Output is correct
46 Correct 584 ms 30636 KB Output is correct
47 Correct 563 ms 30640 KB Output is correct
48 Correct 602 ms 30636 KB Output is correct
49 Correct 989 ms 49140 KB Output is correct
50 Correct 960 ms 49072 KB Output is correct
51 Correct 979 ms 49052 KB Output is correct
52 Correct 1033 ms 49184 KB Output is correct
53 Correct 1054 ms 49092 KB Output is correct
54 Correct 1127 ms 49044 KB Output is correct
55 Execution timed out 1583 ms 77380 KB Time limit exceeded
56 Halted 0 ms 0 KB -