oj.uz

Submission #86808

# Submission time Handle Problem Language Result Execution time Memory
86808 2018-11-27T15:22:17 Z vanbang9710 Divide and conquer (IZhO14_divide) C++14
100 / 100
 48 ms 3328 KB 
#include<iostream>
#include<ctime>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<climits>
#include<cstring>
#include<iomanip>
#include<string>
#include<bitset>
#include<unordered_map>
#include<unordered_set>
#include<set>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<deque>
#include<algorithm>
#include<functional>
#include<chrono>
//#include<windows.h>
//#include<direct.h>
#include<random>
#include<sstream>

#define y0 asdahsdlkahsdad
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define taskname "divide"
//#define GuiltiaSinJurai

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using namespace std;

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

const int maxN = 1e5 + 1;
const ll LInf = 1e15;

struct TMine
{
    int x, g, d;
};
vector<TMine> p;
int n, m;
ll lab[maxN], sg, sd, ans = 0;
vector<ll> v;

inline void Update(int i, ll val) { for (; i <= m; i += i & -i) lab[i] = min(lab[i], val); }
inline ll Get(int i) { ll res = LInf; for (; i > 0; i &= i - 1) res = min(res, lab[i]); return res; }

int main()
{
    #ifdef GuiltiaSinJurai
    auto start = chrono::steady_clock::now();
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(taskname".inp", "r", stdin);
    //freopen(taskname".out", "w", stdout);

    Cin(n);
    sd = 0;
    p.resize(n);
    v.reserve(n);
    for (auto &t : p)
    {
        Cin(t.x); Cin(t.g); Cin(t.d);
        v.push_back(sd - t.x);
        sd += t.d;
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    m = v.size();
    fill_n(lab + 1, m, LInf);
    sg = sd = 0;
    for (auto &t : p)
    {
        Update(upper_bound(v.begin(), v.end(), sd - t.x) - v.begin(), sg);
        ans = max(ans, (sg += t.g) - Get(upper_bound(v.begin(), v.end(), (sd += t.d) - t.x) - v.begin()));
    }
    cout << ans;

    #ifdef GuiltiaSinJurai
    auto end = chrono::steady_clock::now();
    cerr << "In milliseconds : "
         << chrono::duration_cast<chrono::milliseconds>(end - start).count();
    cerr << '\n' << "In seconds : "
         << chrono::duration_cast<chrono::seconds>(end - start).count() << '\n';
    #endif
    return 0;

}

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 380 KB Output is correct
3 Correct 2 ms 552 KB Output is correct
4 Correct 2 ms 552 KB Output is correct
5 Correct 2 ms 552 KB Output is correct
6 Correct 2 ms 580 KB Output is correct
7 Correct 2 ms 580 KB Output is correct
8 Correct 3 ms 580 KB Output is correct
9 Correct 2 ms 580 KB Output is correct
10 Correct 2 ms 580 KB Output is correct
11 Correct 2 ms 592 KB Output is correct
12 Correct 2 ms 608 KB Output is correct

Subtask #2
31.0 / 31.0

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

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 764 KB Output is correct
2 Correct 5 ms 892 KB Output is correct
3 Correct 5 ms 892 KB Output is correct
4 Correct 21 ms 1916 KB Output is correct
5 Correct 24 ms 1916 KB Output is correct
6 Correct 48 ms 3324 KB Output is correct
7 Correct 38 ms 3324 KB Output is correct
8 Correct 45 ms 3324 KB Output is correct
9 Correct 39 ms 3324 KB Output is correct
10 Correct 39 ms 3328 KB Output is correct
11 Correct 42 ms 3328 KB Output is correct
12 Correct 43 ms 3328 KB Output is correct