oj.uz

Submission #86766

# Submission time Handle Problem Language Result Execution time Memory
86766 2018-11-27T09:58:15 Z Mercenary Divide and conquer (IZhO14_divide) C++11
100 / 100
 63 ms 8956 KB 
#include<bits/stdc++.h>
#define pb push_back
#define brokenheart "TEST"
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 enter()
{
    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;
}

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;
}

void solve()
{
    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;
}

int32_t main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
    if(fopen(brokenheart".INP","r"))
        freopen(brokenheart".INP","r",stdin) ,
        freopen(brokenheart".OUT","w",stdout);
    enter();
    solve();
}

Compilation message

divide.cpp: In function 'void enter()':
divide.cpp:30:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1 ; i < v.size() ; ++i)
                     ~~^~~~~~~~~~
divide.cpp: In function 'int32_t main()':
divide.cpp:73:46: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(brokenheart".INP","r",stdin) ,
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
         freopen(brokenheart".OUT","w",stdout);
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
divide.cpp:73:46: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

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

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1820 KB Output is correct
2 Correct 8 ms 2120 KB Output is correct
3 Correct 12 ms 2120 KB Output is correct
4 Correct 28 ms 4700 KB Output is correct
5 Correct 30 ms 4708 KB Output is correct
6 Correct 63 ms 8956 KB Output is correct
7 Correct 50 ms 8956 KB Output is correct
8 Correct 51 ms 8956 KB Output is correct
9 Correct 52 ms 8956 KB Output is correct
10 Correct 50 ms 8956 KB Output is correct
11 Correct 57 ms 8956 KB Output is correct
12 Correct 58 ms 8956 KB Output is correct