oj.uz

Submission #99371

# Submission time Handle Problem Language Result Execution time Memory
99371 2019-03-03T05:11:51 Z kjain_1810 Divide and conquer (IZhO14_divide) C++17
100 / 100
 94 ms 11756 KB 
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn = 1e5 + 5;
#define int ll
 
int n;
int x[maxn] , r[maxn] , g[maxn] , dis[maxn];
int bit[maxn] , cost[maxn] , c[maxn] , sum[maxn];
vector<pair<int,int>> v;
 
void update(int pos , int x)
{
    for( ; pos > 0 ; pos &= pos - 1)
        bit[pos] = min(bit[pos],x);
}
 
int query(int pos)
{
    int res = maxn;
    for( ; pos < maxn ; pos += pos & -pos)
        res = min(res , bit[pos]);
    return res;
}
 
int32_t main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1 ; i <= n ; ++i)
        cin >> x[i] >> g[i] >> r[i];
    for(int i = 1 ; i <= n ; ++i){
        r[i] += r[i - 1];
        sum[i] = sum[i - 1] + g[i];
    }
    for(int i = 1 ; i <= n ; ++i)
        v.pb({x[i]-r[i-1],i});
    sort(v.begin(),v.end());
    int cnt = 1;
    c[v[0].second] = 1;
    vector<pair<int,int>> v1;
    v1.push_back(v[0]);
    for(int i = 1 ; i < v.size() ; ++i)
    {
        if(v[i].first == v[i - 1].first)c[v[i].second] = cnt;
        else c[v[i].second] = ++cnt ,v1.push_back(v[i]);
    }
    v = v1;
    fill_n(bit , maxn , maxn);
    ll res = 0;
    for(int i = 1 ; i <= n ; ++i)
    {
        update(c[i] , i - 1);
        int pos = lower_bound(v.begin(),v.end(),make_pair(x[i] - r[i] , 0ll)) - v.begin();
        int ans = query(pos + 1);
//        cout << ans << " ";
        if(ans != maxn)res = max(res , sum[i] - sum[ans]);
//        res = max(res , g[i]);
    }
    cout << res;
}

Compilation message

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

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1280 KB Output is correct
2 Correct 2 ms 1152 KB Output is correct
3 Correct 4 ms 1152 KB Output is correct
4 Correct 3 ms 1280 KB Output is correct
5 Correct 3 ms 1280 KB Output is correct
6 Correct 4 ms 1280 KB Output is correct
7 Correct 4 ms 1280 KB Output is correct
8 Correct 4 ms 1336 KB Output is correct
9 Correct 4 ms 1408 KB Output is correct
10 Correct 4 ms 1408 KB Output is correct
11 Correct 8 ms 1792 KB Output is correct
12 Correct 7 ms 1792 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1792 KB Output is correct
2 Correct 9 ms 2172 KB Output is correct
3 Correct 9 ms 2172 KB Output is correct
4 Correct 26 ms 5872 KB Output is correct
5 Correct 32 ms 6132 KB Output is correct
6 Correct 64 ms 11756 KB Output is correct
7 Correct 94 ms 10676 KB Output is correct
8 Correct 53 ms 10604 KB Output is correct
9 Correct 55 ms 10348 KB Output is correct
10 Correct 50 ms 10448 KB Output is correct
11 Correct 59 ms 10860 KB Output is correct
12 Correct 60 ms 11116 KB Output is correct