Submission #340844

#	Time	Username	Problem	Language	Result	Execution time	Memory
340844		mehrdad_sohrabi	Arranging Tickets (JOI17_arranging_tickets)	C++14	0 / 100	761 ms	504 KiB

arranging_tickets

#include <bits/stdc++.h>
/// 500 485
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
//#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
using namespace std;
const int N=2e5+100;
ll a[N];
    ll n,m;
void add(ll l,ll r,ll val){
    for (int i=l+1;i!=r%n+1;i=i%n+1){
        a[i]+=val;
    }
}
ll get(ll l,ll r){
    ll mx0=0;
    for (int i=l+1;i!=r%n+1;i=i%n+1){
        mx0=max(mx0,a[i]);
    }
    return mx0;
}
int32_t main(){
    cin >> n >> m ;
    vector <pair <int,pii> > q;
    for (int i=1;i<=m;i++){
        ll l,r,c;
        cin >> l >> r >> c;
        if ((r-l+n)%n>(l-r+n)%n) swap(l,r);
        q.pb({(r-l+n)%n,{l,r}});
        add(l,r,1);
    }
    for (int i=0;i<N;i++){
        for (int i=0;i<q.size();i++){
            ll l=q[i].S.F,r=q[i].S.S;
            add(l,r,-1);
            ll mx0=get(l,r);
            ll mx1=get(r,l);
            if (mx0==mx1){
                ll z=rand()%2;
                if (z){
                    add(l,r,1);
                    continue;
                }
                else add(r,l,1);
            }
            if (mx0<mx1){
                add(l,r,1);
            }
            else add(r,l,1);
        }
    }
    ll ans=0;
    for (int i=1;i<=n;i++) ans=max(ans,a[i]);
    cout << ans << endl;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 35
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 15