oj.uz

답안 #340843

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
340843 2020-12-28T12:33:11 Z mehrdad_sohrabi Arranging Tickets (JOI17_arranging_tickets) C++14
0 / 100
 1 ms 364 KB 
#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<m;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.0

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

Subtask #2
0 / 35.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 15.0

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