oj.uz

Submission #86734

# Submission time Handle Problem Language Result Execution time Memory
86734 2018-11-27T08:27:13 Z HellAngel Divide and conquer (IZhO14_divide) C++14
100 / 100
 174 ms 19576 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 3e5 + 7;
int n, m, x[maxn], g[maxn], r[maxn];
int BIT[maxn], cnt, ans;
vector<int> vt;

map<int, int> mp;

void Update(int x, int val)
{
    for(; x < maxn; x += (x & -x))
    {
        BIT[x] = min(BIT[x], val);
    }
}

int Get(int x)
{
    int ans = INT_MAX;
    for(; x > 0; x -= (x & -x))
    {
        ans = min(ans, BIT[x]);
    }
    return ans;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    fill_n(BIT, maxn, INT_MAX);
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> x[i] >> g[i] >> r[i];
        ans = max(ans, g[i]);
        r[i] += r[i - 1];
        g[i] += g[i - 1];
        vt.push_back(r[i] - x[i]);
        vt.push_back(r[i - 1] - x[i]);
    }
    sort(vt.begin(), vt.end());
    mp[vt[0]] = ++cnt;
    for(int i = 1; i < vt.size(); i++)
    {
        if(vt[i] == vt[i - 1]) continue;
        mp[vt[i]] = ++cnt;
    }
    for(int i = 1; i <= n; i++)
    {
        int gau = mp[r[i] - x[i]];
        int meo = mp[r[i - 1] - x[i]];
        int hihi = Get(gau);
        if(hihi != INT_MAX) ans = max(ans, g[i] - g[hihi - 1]);
        Update(meo, i);
    }
    cout << ans;
}

Compilation message

divide.cpp: In function 'int32_t main()':
divide.cpp:48:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i < vt.size(); i++)
                    ~~^~~~~~~~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2988 KB Output is correct
2 Correct 5 ms 2988 KB Output is correct
3 Correct 4 ms 3068 KB Output is correct
4 Correct 4 ms 3068 KB Output is correct
5 Correct 5 ms 3068 KB Output is correct
6 Correct 5 ms 3196 KB Output is correct
7 Correct 6 ms 3196 KB Output is correct
8 Correct 5 ms 3196 KB Output is correct
9 Correct 5 ms 3196 KB Output is correct
10 Correct 6 ms 3324 KB Output is correct
11 Correct 10 ms 3836 KB Output is correct
12 Correct 10 ms 3836 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3836 KB Output is correct
2 Correct 15 ms 4604 KB Output is correct
3 Correct 17 ms 4604 KB Output is correct
4 Correct 77 ms 11200 KB Output is correct
5 Correct 106 ms 11200 KB Output is correct
6 Correct 173 ms 19576 KB Output is correct
7 Correct 157 ms 19576 KB Output is correct
8 Correct 155 ms 19576 KB Output is correct
9 Correct 158 ms 19576 KB Output is correct
10 Correct 159 ms 19576 KB Output is correct
11 Correct 169 ms 19576 KB Output is correct
12 Correct 174 ms 19576 KB Output is correct