oj.uz

Submission #198802

# Submission time Handle Problem Language Result Execution time Memory
198802 2020-01-27T18:23:20 Z Vladikus004 Divide and conquer (IZhO14_divide) C++14
0 / 100
 9 ms 3320 KB 
#include <bits/stdc++.h>
#define inf 2e9
#define ff first
#define ss second
#define all(v) v.begin() , v.end()
using namespace std;
typedef long long ll;
typedef pair <ll, int> pii;

const int N = 100000 + 5;

struct obj{
    int x, d, g;
    obj(){
        x = g = d = 0;
    }
};

int n;
ll pref[N], fenw[2 * N], pref_g[N];
obj a[N];

void up(int ind, ll x){
    for (int i = ind; i <= 2 * N; i |= i + 1)
        fenw[i] = min(fenw[i], x);
}

ll get_min(int ind){
    ll ans = inf;
    for (int i = ind; i >= 0; i = (i & (i + 1)) - 1)
        ans = min(ans, fenw[i]);
    return ans;
}

void init(){
    for (int i = 0; i <= 2 * N; i++)
        fenw[i] = inf;
}

map <ll, int> code;

int main()
{
    #ifdef VBH
        freopen("input.txt" , "r" , stdin);
    #endif
        freopen("divide.in" , "r" , stdin);
        freopen("divide.out" , "w" , stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    init();
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i].x >> a[i].g >> a[i].d;
    for (int i = 1; i <= n; i++){
        pref_g[i] = a[i].g;
        pref_g[i] += pref_g[i - 1];
        pref[i] = a[i].d;
        pref[i] += pref[i - 1];
    }
    vector <ll> roman;
    for (int i = 1; i <= n; i++){
        roman.push_back(-a[i].x + pref[i]);
        roman.push_back(-a[i].x + pref[i - 1]);
    }
    sort(roman.begin(), roman.end());
    for (int i = 0; i < roman.size(); i++)
        code[roman[i]] = i;
    ll ans = 0;
    for (int i = 1; i <= n; i++){
        ans = max(ans, (ll)a[i].g);
        int ind = code[-a[i].x + pref[i]];
        ll mn = get_min(ind);
        if (mn != inf)
            ans = max(ans, pref_g[i] - pref_g[mn - 1]);
        ind = code[-a[i].x + pref[i - 1]];
        up(ind, i);
    }
    cout << ans;
    return 0;
}

Compilation message

divide.cpp: In function 'int main()':
divide.cpp:67:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < roman.size(); i++)
                     ~~^~~~~~~~~~~~~~
divide.cpp:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("divide.in" , "r" , stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
divide.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("divide.out" , "w" , stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
divide.cpp: In function 'void init()':
divide.cpp:37:17: warning: iteration 200010 invokes undefined behavior [-Waggressive-loop-optimizations]
         fenw[i] = inf;
                 ^
divide.cpp:36:23: note: within this loop
     for (int i = 0; i <= 2 * N; i++)
                     ~~^~~~~~~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 3320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 3064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 3064 KB Output isn't correct
2 Halted 0 ms 0 KB -