Submission #84444

#	Time	Username	Problem	Language	Result	Execution time	Memory
84444		someone_aa	Job Scheduling (CEOI12_jobs)	C++17	40 / 100	603 ms	20420 KiB

jobs

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100100;
struct node {
public:
    int value, ind;
};
node tree[3*maxn];

int n, d, m;
vector<int>tasks[maxn];

node mergef(node a, node b) {
    node c;
    if(a.value < b.value) {
        c.value = a.value;
        c.ind = a.ind;
    }
    else if(a.value > b.value) {
        c.value = b.value;
        c.ind = b.ind;
    }
    else if(a.value == b.value){
        c.value = a.value;
        c.ind = min(a.ind, b.ind);
    }
    return c;
}

void build(int li=1, int ri=n, int index=1) {
    if(li == ri) {
        tree[index].value = 0;
        tree[index].ind = li;
    }
    else {
        int mid = (li+ri)/2;
        build(li,mid,2*index);
        build(mid+1,ri,2*index+1);
        tree[index] = mergef(tree[2*index], tree[2*index+1]);
    }
}

void update(int x, int li=1, int ri=n, int index=1) {
    if(li == ri) {
        tree[index].value++;
        tree[index].ind = x;
    }
    else {
        int mid = (li+ri)/2;
        if(x <= mid) update(x, li, mid, 2*index);
        else update(x, mid+1,ri,2*index+1);
        tree[index] = mergef(tree[2*index], tree[2*index+1]);
    }
}

node query(int ql, int qr, int li=1, int ri=n, int index=1) {
    if(li > qr || ri < ql) return {INT_MAX, INT_MAX};
    else if(li >= ql && ri <= qr) return tree[index];
    else {
        int mid = (li+ri)/2;
        return mergef(query(ql,qr,li,mid,2*index), query(ql,qr,mid+1,ri,2*index+1));
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>d>>m;
    build();
    int x, result = 0;
    for(int i=1;i<=m;i++) {
        cin>>x;
        node curr = query(x, x+d);
        //cout<<"["<<x<<", "<<x+d<<"] -> "<<curr.value<<", "<<curr.ind<<"\n";
        tasks[curr.ind].pb(i);
        result = max(result, int(tasks[curr.ind].size()));
        update(curr.ind);
    }
    cout<<result<<"\n";

    for(int i=1;i<=n;i++) {
        for(int j:tasks[i]) {
            cout<<j<<" ";
        } cout<<"0\n";
    }

    return 0;
}

• Subtask 1: 40 / 100