oj.uz

Submission #171379

# Submission time Handle Problem Language Result Execution time Memory
171379 2019-12-28T13:09:23 Z Swan Divide and conquer (IZhO14_divide) C++14
100 / 100
 252 ms 23652 KB 
#include <bits/stdc++.h>
#define stop system("pause")
#define stop2 char o; cin >> o
#define INP freopen("pcb.in","r",stdin)
#define OUTP freopen ("pcb.out","w",stdout)
#define int long long
using namespace std;

const int maxn = 2e5+228;

struct st{
    int x;
    int d;
    int g;
    st(int xx,int gg,int dd){
        x = xx;
        d = dd;
        g = gg;
    }
    bool operator<(st b)const{
        return x < b.x;
    }
};

vector<st> v;
int tree[5*maxn];

void build(int v,int l,int r){
    if(l == r){
        tree[v] = 1e16;
        return;
    }
    int m = (l+r)/2;
    build(v*2,l,m);
    build(v*2+1,m+1,r);
    tree[v] = 1e16;
}

void upd(int v,int l,int r,int need,int x){
    if(l == r){
        tree[v] = min(x,tree[v]);
        return;
    }
    int m = (l+r)/2;
    if(need<=m)upd(v*2,l,m,need,x);
    else upd(v*2+1,m+1,r,need,x);
    tree[v] = min(tree[v*2],tree[v*2+1]);
}

int get_min(int v,int l,int r,int le,int re){
    if(l>=le && r <= re){
        return tree[v];
    }
    if(l > re || r < le)return 1e16;
    int m = (l+r)/2;
    int a = get_min(v*2,l,m,le,re);
    int b = get_min(v*2+1,m+1,r,le,re);
    return min(a,b);
}

int pref1[maxn],pref2[maxn],gold[maxn];
unordered_map<int,int> irl;
unordered_map<int,int> cmp;
vector<int> w;

main(){
    ios_base::sync_with_stdio(0);
    int n; cin >> n;
    for(int i(0); i < n;i++){
        int x,g,d; cin >> x >> g >> d;
        v.push_back({x,g,d});
    }
    sort(v.begin(),v.end());
    pref1[0] = v[0].d;
    set<int> s;
    s.insert(v[0].x-pref2[0]);
    gold[0] = v[0].g;
    for(int i(1);i < n;i++){
        pref2[i] = pref1[i-1];
        pref1[i] = pref1[i-1]+v[i].d;
        gold[i] = gold[i-1]+v[i].g;
        s.insert(v[i].x-pref2[i]);
    }
    int pnt = 0;
    for(auto&a : s){
        w.push_back(a);
        cmp[a] = pnt;
        irl[pnt] = a;
        pnt++;
    }
    build(1,0,pnt-1);
    int ans = 0;
    for(int i(0); i < v.size();i++){
        //cout << v[i].x << endl;
        ans = max(ans,v[i].g);
        int now = v[i].x-pref1[i];
        int best = lower_bound(w.begin(),w.end(),now)-w.begin();
        int to;
        if(best != w.size()){
            to = get_min(1,0,pnt-1,best,w.size()-1);
        }else to = 1e17;
        //cout << to << ' ' << gold[i] << endl;
        upd(1,0,pnt-1,cmp[v[i].x-pref2[i]],gold[i]-v[i].g);
        ans = max(ans,gold[i]-to);
    }
    cout << ans;
}
/*
*/

Compilation message

divide.cpp:66:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
divide.cpp: In function 'int main()':
divide.cpp:93:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i(0); i < v.size();i++){
                   ~~^~~~~~~~~~
divide.cpp:99:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(best != w.size()){
            ~~~~~^~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 508 KB Output is correct
5 Correct 4 ms 508 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 4 ms 632 KB Output is correct
8 Correct 4 ms 632 KB Output is correct
9 Correct 4 ms 632 KB Output is correct
10 Correct 5 ms 636 KB Output is correct
11 Correct 9 ms 1464 KB Output is correct
12 Correct 10 ms 1464 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1464 KB Output is correct
2 Correct 22 ms 2676 KB Output is correct
3 Correct 17 ms 2804 KB Output is correct
4 Correct 109 ms 11496 KB Output is correct
5 Correct 106 ms 11752 KB Output is correct
6 Correct 252 ms 23652 KB Output is correct
7 Correct 238 ms 22240 KB Output is correct
8 Correct 249 ms 22484 KB Output is correct
9 Correct 221 ms 22244 KB Output is correct
10 Correct 216 ms 21984 KB Output is correct
11 Correct 227 ms 22880 KB Output is correct
12 Correct 227 ms 22884 KB Output is correct