제출 #1204105

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1204105		Sir_Ahmed_Imran	Arranging Tickets (JOI17_arranging_tickets)	C++17	10 / 100	6 ms	9804 KiB

arranging_tickets

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

#include <bits/stdc++.h>
using namespace std;
#define N 100001
#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[4 * N];
int lazy[4 * N];
vector<pii> mr[4 *N];

void built(int v = 1, int s = 0, int e = n){
    mr[v] = {{0, 0}};
    mx[v] = lazy[v] = 0;
    if(e - s == 1) return;
    int lc, rc, mid;
    lc = 2 * v;
    rc = 2 * v + 1;
    mid = (s + e) / 2;
    built(lc, s, mid);
    built(rc, mid, e);
}

void push(int v){
    int lc, rc;
    lc = 2 * v;
    rc = lc + 1;
    mx[v] += lazy[v];
    lazy[lc] += lazy[v];
    lazy[rc] += lazy[v];
    lazy[v] = 0;
}

void add(int l, int r, int val, int v = 1, int s = 0, int e = n){
    push(v);
    if(r <= s || e <= l || r <= l) return;
    if(l <= s && e <= r){
        lazy[v] += val;
        push(v);
        return;
    }
    int lc, rc, mid;
    push(v);
    lc = 2 * v;
    rc = 2 * v + 1;
    mid = (s + e) / 2;
    add(l, r, val, lc, s, mid);
    add(l, r, val, rc, mid, e);
    mx[v] = max(mx[lc], mx[rc]);
}

pii get(int v = 1, int s = 0, int e = n){
    push(v);
    if(mx[v] <= x) return mr[v].back();
    if(e - s == 1) return {0, 0};
    pii pi, pj;
    int lc, rc, mid;
    lc = 2 * v;
    rc = 2 * v + 1;
    mid = (s + e) / 2;
    pi = pj = get(lc, s, mid);
    if(mx[lc] <= x)
        pj = get(rc, mid, e);
    if(pj.ss > pi.ss)
        swap(pi, pj);
    return pi;
}

int get_mx(int l, int r, int v = 1, int s = 0, int e = n){
    push(v);
    if(r <= s || e <= l || r <= l) return 0;
    if(l <= s && e <= r) return mx[v];
    int lc, rc, mid;
    lc = 2 * v;
    rc = 2 * v + 1;
    mid = (s + e) / 2;
    return max(get_mx(l, r, lc, s, mid), get_mx(l, r, rc, mid, e));
}

void Insert(int l, int r, int v = 1, int s = 0, int e = n){
    push(v);
    if(e - s == 1){
        mr[v].append({l, r});
        return;
    }
    int lc, rc, mid;
    lc = 2 * v;
    rc = 2 * v + 1;
    mid = (s + e) / 2;
    if(l < mid) Insert(l, r, lc, s, mid);
    else Insert(l, r, rc, mid, e);
    mr[v].clear();
    if(mr[rc].back().ss > mr[lc].back().ss)
        mr[v].append(mr[rc].back());
    else mr[v].append(mr[lc].back());
}

void remove(int l, int v = 1, int s = 0, int e = n){
    push(v);
    if(e - s == 1){
        mr[v].pop_back();
        return;
    }
    int lc, rc, mid;
    lc = 2 * v;
    rc = 2 * v + 1;
    mid = (s + e) / 2;
    if(l < mid) remove(l, lc, s, mid);
    else remove(l, rc, mid, e);
    mr[v].clear();
    if(mr[rc].back().ss > mr[lc].back().ss)
        mr[v].append(mr[rc].back());
    else mr[v].append(mr[lc].back());
}

bool check(int c){
    x = c;
    pii pi;
    built();
    for(auto & [i, j] : q){
        add(i + 1, j + 1, 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, 1);
            add(pi.ss + 1, n, 1);
            add(pi.ff + 1, pi.ss + 1, -1);
        }
    }
    return 1;
}

void solve(){
    int l, r, c;
    cin >> n >> m;
    n++;
    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});
    }
    sort(all(q));
    int ans = 0;
    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: 10 / 10
• Subtask 2: 0 / 35
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 15