oj.uz

Submission #86749

# Submission time Handle Problem Language Result Execution time Memory
86749 2018-11-27T09:08:12 Z Kamisama Divide and conquer (IZhO14_divide) C++14
100 / 100
 122 ms 15552 KB 
#include <bits/stdc++.h>
#define up(i,a,b) for(int i=a;i<=b;i++)
#define down(i,a,b) for(int i=a;i>=b;i--)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repd(i,a,b) for(int i=a;i>b;i--)
#define self (*this)
#define pb push_back
#define cntbit(x) __builtin_popcountll(x)
#define x first
#define y second

using namespace std;

typedef long long ll;

const int maxn=2e5+7;
const ll mod=1e15+7;
const int inf=1e9+7;
const ll linf=1e16+7;
const double esp=1e-6;

int n;
ll x[maxn],X[maxn],g[maxn],r[maxn],bit[maxn],res;

template<typename T> inline void Read(T &x){
    register char c;
    bool neg=false;
    for(c=getchar();c<'0'||c>'9';c=getchar()) if(c=='-') neg=true;
    for(x=0;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';
    if(neg) x=-x;
}

template<typename T> inline void Write(T x){
    if(x<0) putchar('-'), x=-x;
    if(x>9) Write(x/10);
    putchar(x%10+'0');
}

inline void Enter(){
    Read(n);
    up(i,1,n) Read(X[i]),Read(g[i]),Read(r[i]),g[i]+=g[i-1],r[i]+=r[i-1];
    up(i,1,n) x[i]=r[i-1]-X[i];
    up(i,n+1,2*n) x[i]=r[i-n]-X[i-n];
}

inline void Update(int x, const ll &val){
    for(;x<maxn;x+=x&-x) bit[x]=min(bit[x],val);
}

inline ll Get(int x){
    ll res=linf;
    for(;x;x-=x&-x) res=min(res,bit[x]);
    return res;
}

inline void Compress(){
    set<ll> Set;
    up(i,1,2*n) Set.insert(x[i]);
    vector<ll> Tmp(Set.begin(),Set.end());
    //up(i,1,2*n) cout<<"x["<<i<<"]= "<<x[i]<<'\n';
    up(i,1,2*n) x[i]=lower_bound(Tmp.begin(),Tmp.end(),x[i])-Tmp.begin()+1;
    //up(i,1,2*n) cout<<"x["<<i<<"]= "<<x[i]<<'\n';
}

inline void Solve(){
    fill(bit+1,bit+maxn,linf);
    up(i,1,n){
        Update(x[i],g[i-1]);
        ll Gold=Get(x[i+n]);
        res=max(res,g[i]-Gold);
        //cerr<<res<<' '<<Gold<<'\n';
    }
    Write(res);
}

inline void Main(){
    Enter();
    Compress();
    Solve();
}

inline void Execution_Time_Calculator(const bool &Allow){
    auto start = chrono::steady_clock::now();
    Main();
    if(not Allow) return;
    auto end=chrono::steady_clock::now();
    cerr<<"\n\nIn milliseconds: "
        <<chrono::duration_cast<chrono::milliseconds>(end-start).count();
    cerr<<'\n' << "In seconds: "<<fixed<<setprecision(3)
        <<(double)chrono::duration_cast<chrono::milliseconds>(end-start).count()/1000<<'\n';
}

inline void Input_Output_From_File(const bool &Allow){
    if(not Allow) return;
    #define task "TEST"
    freopen(task".INP","r",stdin);
    freopen(task".OUT","w",stdout);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);

    Input_Output_From_File(0);
    Execution_Time_Calculator(0);

    return 0;
}

Compilation message

divide.cpp: In function 'void Input_Output_From_File(const bool&)':
divide.cpp:96:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(task".INP","r",stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
divide.cpp:97:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(task".OUT","w",stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1912 KB Output is correct
2 Correct 3 ms 2036 KB Output is correct
3 Correct 3 ms 2112 KB Output is correct
4 Correct 3 ms 2112 KB Output is correct
5 Correct 3 ms 2112 KB Output is correct
6 Correct 4 ms 2112 KB Output is correct
7 Correct 4 ms 2208 KB Output is correct
8 Correct 4 ms 2240 KB Output is correct
9 Correct 3 ms 2240 KB Output is correct
10 Correct 4 ms 2240 KB Output is correct
11 Correct 3 ms 2240 KB Output is correct
12 Correct 4 ms 2240 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2240 KB Output is correct
2 Correct 4 ms 2240 KB Output is correct
3 Correct 4 ms 2300 KB Output is correct
4 Correct 5 ms 2300 KB Output is correct
5 Correct 4 ms 2300 KB Output is correct
6 Correct 5 ms 2300 KB Output is correct
7 Correct 4 ms 2312 KB Output is correct
8 Correct 4 ms 2312 KB Output is correct
9 Correct 5 ms 2472 KB Output is correct
10 Correct 5 ms 2472 KB Output is correct
11 Correct 7 ms 2940 KB Output is correct
12 Correct 8 ms 2940 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2940 KB Output is correct
2 Correct 11 ms 3540 KB Output is correct
3 Correct 12 ms 3540 KB Output is correct
4 Correct 44 ms 8796 KB Output is correct
5 Correct 54 ms 8800 KB Output is correct
6 Correct 122 ms 15484 KB Output is correct
7 Correct 113 ms 15552 KB Output is correct
8 Correct 111 ms 15552 KB Output is correct
9 Correct 94 ms 15552 KB Output is correct
10 Correct 106 ms 15552 KB Output is correct
11 Correct 110 ms 15552 KB Output is correct
12 Correct 104 ms 15552 KB Output is correct