Submission #84448

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
84448	2018-11-15T08:03:08 Z	someone_aa	Job Scheduling (CEOI12_jobs)	C++17	40 / 100	590 ms	15788 KB

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);
    }
    for(int i=1;i<=n;i++) {
        result = max(result,int(tasks[i].size()));
    }
    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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	4212 KB	Output is correct
2	Correct	46 ms	4340 KB	Output is correct
3	Correct	44 ms	4340 KB	Output is correct
4	Correct	49 ms	4340 KB	Output is correct
5	Correct	48 ms	4464 KB	Output is correct
6	Correct	49 ms	4464 KB	Output is correct
7	Correct	44 ms	4464 KB	Output is correct
8	Correct	40 ms	4464 KB	Output is correct
9	Incorrect	57 ms	6400 KB	Output isn't correct
10	Incorrect	54 ms	6464 KB	Output isn't correct
11	Incorrect	64 ms	6464 KB	Output isn't correct
12	Incorrect	121 ms	6464 KB	Output isn't correct
13	Incorrect	177 ms	7184 KB	Output isn't correct
14	Incorrect	304 ms	8720 KB	Output isn't correct
15	Incorrect	251 ms	8720 KB	Output isn't correct
16	Incorrect	413 ms	10316 KB	Output isn't correct
17	Incorrect	507 ms	13740 KB	Output isn't correct
18	Incorrect	476 ms	13740 KB	Output isn't correct
19	Incorrect	590 ms	15788 KB	Output isn't correct
20	Incorrect	506 ms	15788 KB	Output isn't correct