Submission #1205298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205298		Sir_Ahmed_Imran	Arranging Tickets (JOI17_arranging_tickets)	C++17	0 / 100	3 ms	4936 KiB

arranging_tickets

            //    01001100 01001111 01010100 01000001    \\
            //                                           \\
            //                ╦  ╔═╗╔╦╗╔═╗               \\
            //                ║  ║ ║ ║ ╠═╣               \\
            //                ╩═╝╚═╝ ╩ ╩ ╩               \\
            //                                           \\
            //    01001100 01001111 01010100 01000001    \\

#include <bits/stdc++.h>
using namespace std;
#define N 200002
#define nl '\n'
#define ff first
#define ss second
#define add insert
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

int n, m, x;
vector<pii> q;
int mx[N];
int cnt[N];
vector<int> mr[N];

void built(){
    for(int i = 0; i < n; i++){
        mr[i] = {0};
        mx[i] = cnt[i] = 0;
    }
}

void add(int l, int r, int val){
    for(int i = l; i < r; i++)
        mx[i] += val;
}

pii get(){
    pii pi = {0, 0};
    for(int i = 1; i < n && mx[i] <= x; i++)
        if(mr[i].back() > pi.ss) pi = {i, mr[i].back()};
    return pi;
}

int get_mx(int l, int r){
    int ans = 0;
    for(int i = l; i < r; i++)
        ans = max(ans, mx[i]);
    return ans;
}

void Insert(int l, int r){
    mr[l].append(r);
}

void remove(int l){
    mr[l].pop_back();
}

bool check(int c){
    x = c;
    pii pi;
    built();
    for(auto & [i, j] : q){
        cnt[i]++;
        if(cnt[i] > x){
            add(0, i, 1);
            add(j, n, 1);
        }
        else{
            add(i, j, 1);
            Insert(i, j);
        }
        while(get_mx(0, n) > x){
            pi = get();
            if(!pi.ff) return 0;
            remove(pi.ff);
            add(0, pi.ff, 1);
            add(pi.ss, n, 1);
            add(pi.ff, pi.ss, -1);
        }
    }
    return 1;
}

void solve(){
    int l, r, c;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> l >> r >> c;
        if(l > r) swap(l, r);
        for(int j = 0; j < c; j++)
            q.append({l, r});
    }
    int ans = 0;
    sort(all(q));
    for(int i = 65536; i > 0; i /= 2)
        if(!check(ans + i)) ans += i;
    cout << ans + 1;
}

int terminator(){
    L0TA;
    solve();
    return 0;
}

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