oj.uz

Submission #198807

# Submission time Handle Problem Language Result Execution time Memory
198807 2020-01-27T18:25:36 Z Vladikus004 Divide and conquer (IZhO14_divide) C++14
100 / 100
 139 ms 22760 KB 
#include <bits/stdc++.h>
#define inf 2e9
#define ff first
#define ss second
#define all(v) v.begin() , v.end()
#define int long long
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;

int32_t 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 < (int)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 'void init()':
divide.cpp:38:17: warning: iteration 200010 invokes undefined behavior [-Waggressive-loop-optimizations]
         fenw[i] = inf;
                 ^
divide.cpp:37:23: note: within this loop
     for (int i = 0; i <= 2 * N; i++)
                     ~~^~~~~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4344 KB Output is correct
2 Correct 8 ms 4344 KB Output is correct
3 Correct 8 ms 4344 KB Output is correct
4 Correct 8 ms 4344 KB Output is correct
5 Correct 8 ms 4344 KB Output is correct
6 Correct 9 ms 4472 KB Output is correct
7 Correct 9 ms 4472 KB Output is correct
8 Correct 10 ms 4472 KB Output is correct
9 Correct 9 ms 4600 KB Output is correct
10 Correct 10 ms 4600 KB Output is correct
11 Correct 13 ms 5112 KB Output is correct
12 Correct 13 ms 5112 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5112 KB Output is correct
2 Correct 19 ms 5880 KB Output is correct
3 Correct 19 ms 6008 KB Output is correct
4 Correct 69 ms 13164 KB Output is correct
5 Correct 69 ms 13424 KB Output is correct
6 Correct 139 ms 22760 KB Output is correct
7 Correct 130 ms 21740 KB Output is correct
8 Correct 131 ms 21736 KB Output is correct
9 Correct 130 ms 21480 KB Output is correct
10 Correct 132 ms 21096 KB Output is correct
11 Correct 130 ms 21992 KB Output is correct
12 Correct 136 ms 22248 KB Output is correct