oj.uz

답안 #89146

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
89146 2018-12-10T15:21:36 Z nikolapesic2802 Arranging Tickets (JOI17_arranging_tickets) C++14
0 / 100
 13 ms 9896 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ll long long
#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a) {
	os << '{';
	for(int i=0;i<sz(a);i++)
	{
		if(i>0&&i<sz(a)-1)
			os << ", ";
		os << a[i];
	}
	os << '}';
    return os;
}
const int N=2e5+5;
vector<vector<pair<int,int> > > interval(N);
vector<ll> sum(N),temp(N),change(N);
int n;
bool test(ll max_flips,ll height)
{
    fill(all(temp),0);
    ll cnt=0;
    priority_queue<pair<int,pair<int,int> > > q;
    for(int i=1;i<=n;i++)
    {
        temp[i]+=temp[i-1];
        for(auto p:interval[i])
            q.push({p.first,{p.second,n-i}});
        ll now=sum[i]+temp[i];
        while(!q.empty()&&now>height)
        {
            int y=q.top().first,c=q.top().second.first,x=n-q.top().second.second;
            ll v=min((ll)c,(ll)(now-height+1)/2);
            q.pop();
            if(y<=i)
                continue;
            cnt+=v;
            temp[i]-=2*v;
            temp[y]+=2*v;
            now-=v;
            if(v<c)
                q.push({y,{c-v,x}});
        }
        if(cnt>max_flips||now>height)
            return false;
    }
    return true;
}
int main()
{
    int m;
    scanf("%i %i",&n,&m);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        scanf("%i %i %i",&a,&b,&c);
        if(a>b)
            swap(a,b);
        interval[a].pb({b,c});
        sum[a]+=c;
        sum[b]-=c;
    }
    ll maxV=0;
    for(int i=1;i<=n;i++)
        sum[i]+=sum[i-1],maxV=max(maxV,sum[i]);
    ll l=0,r=maxV;
    ll ans=-1;
    while(l<r)
    {
        ll mid=(l+r)>>1;
        if(test(maxV-mid,2*mid-maxV)||test(maxV-mid+1,2*mid-maxV-1))
            r=mid;
        else
            l=mid+1;
    }
    printf("%lld\n",l);
    return 0;
}

Compilation message

arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i %i",&n,&m);
     ~~~~~^~~~~~~~~~~~~~~
arranging_tickets.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i %i %i",&a,&b,&c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 9720 KB Output is correct
2 Correct 13 ms 9724 KB Output is correct
3 Incorrect 12 ms 9896 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 9720 KB Output is correct
2 Correct 13 ms 9724 KB Output is correct
3 Incorrect 12 ms 9896 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 9720 KB Output is correct
2 Correct 13 ms 9724 KB Output is correct
3 Incorrect 12 ms 9896 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 9720 KB Output is correct
2 Correct 13 ms 9724 KB Output is correct
3 Incorrect 12 ms 9896 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 9720 KB Output is correct
2 Correct 13 ms 9724 KB Output is correct
3 Incorrect 12 ms 9896 KB Output isn't correct
4 Halted 0 ms 0 KB -