oj.uz

Submission #86764

# Submission time Handle Problem Language Result Execution time Memory
86764 2018-11-27T09:44:51 Z Mercenary Divide and conquer (IZhO14_divide) C++11
0 / 100
 70 ms 10584 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)
        dis[i] = x[i + 1] - x[i];
    for(int i = 1 ; i < n ; ++i){
        cost[i] = cost[i - 1] + dis[i] - r[i];
        v.pb({cost[i],i});
    }
    v.pb({0,0});
    sort(v.begin(),v.end());
    for(int i = 1 ; i <= n ; ++i)
        sum[i] = sum[i - 1] + g[i];
    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 < maxn ; pos += pos & -pos)
        bit[pos] = min(bit[pos],x);
}

int query(int pos)
{
    int res = maxn;
    for( ; pos > 0 ; pos &= pos - 1)
        res = min(res , bit[pos]);
    return res;
}

void solve()
{
    fill_n(bit , maxn , maxn);
    ll res = 0;
    for(int i = 1 ; i <= n ; ++i)
    {
        int pos = upper_bound(v.begin(),v.end(),make_pair(r[i] - cost[i - 1] , 0ll)) - v.begin();
        int ans = query(pos);
        if(ans != maxn)res = max(res , sum[i] - sum[ans]);
        if(i != n)update(c[i] , i - 1);
        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:33: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:75: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:75:46: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Incorrect 3 ms 1280 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1280 KB Output is correct
2 Correct 3 ms 1280 KB Output is correct
3 Incorrect 4 ms 1280 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1672 KB Output is correct
2 Correct 8 ms 2228 KB Output is correct
3 Correct 8 ms 2272 KB Output is correct
4 Correct 28 ms 5528 KB Output is correct
5 Correct 36 ms 5528 KB Output is correct
6 Correct 70 ms 10404 KB Output is correct
7 Correct 67 ms 10448 KB Output is correct
8 Correct 60 ms 10468 KB Output is correct
9 Correct 50 ms 10468 KB Output is correct
10 Incorrect 63 ms 10584 KB Output isn't correct
11 Halted 0 ms 0 KB -