oj.uz

Submission #86732

# Submission time Handle Problem Language Result Execution time Memory
86732 2018-11-27T08:22:57 Z Kamisama Divide and conquer (IZhO14_divide) C++14
100 / 100
 136 ms 24580 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;
 
inline void Enter(){
    cin>>n;
    up(i,1,n) cin>>X[i]>>g[i]>>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';
    }
    cout<<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:82: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:83: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 3 ms 1912 KB Output is correct
2 Correct 3 ms 1920 KB Output is correct
3 Correct 4 ms 1984 KB Output is correct
4 Correct 3 ms 2004 KB Output is correct
5 Correct 3 ms 2056 KB Output is correct
6 Correct 4 ms 2060 KB Output is correct
7 Correct 3 ms 2192 KB Output is correct
8 Correct 3 ms 2192 KB Output is correct
9 Correct 3 ms 2288 KB Output is correct
10 Correct 3 ms 2288 KB Output is correct
11 Correct 3 ms 2288 KB Output is correct
12 Correct 3 ms 2288 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2288 KB Output is correct
2 Correct 4 ms 2288 KB Output is correct
3 Correct 4 ms 2324 KB Output is correct
4 Correct 4 ms 2336 KB Output is correct
5 Correct 4 ms 2420 KB Output is correct
6 Correct 4 ms 2524 KB Output is correct
7 Correct 4 ms 2524 KB Output is correct
8 Correct 4 ms 2524 KB Output is correct
9 Correct 6 ms 2660 KB Output is correct
10 Correct 6 ms 2832 KB Output is correct
11 Correct 8 ms 3380 KB Output is correct
12 Correct 9 ms 3492 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3492 KB Output is correct
2 Correct 11 ms 4280 KB Output is correct
3 Correct 13 ms 4408 KB Output is correct
4 Correct 58 ms 10816 KB Output is correct
5 Correct 80 ms 12196 KB Output is correct
6 Correct 136 ms 19976 KB Output is correct
7 Correct 108 ms 19976 KB Output is correct
8 Correct 116 ms 19976 KB Output is correct
9 Correct 105 ms 19976 KB Output is correct
10 Correct 100 ms 19976 KB Output is correct
11 Correct 128 ms 22216 KB Output is correct
12 Correct 112 ms 24580 KB Output is correct