Submission #84444

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
84444	2018-11-15T07:59:08 Z	someone_aa	Job Scheduling (CEOI12_jobs)	C++17	40 / 100	603 ms	20420 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);
    }
    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	4468 KB	Output is correct
2	Correct	46 ms	4968 KB	Output is correct
3	Correct	44 ms	5292 KB	Output is correct
4	Correct	48 ms	5424 KB	Output is correct
5	Correct	45 ms	5792 KB	Output is correct
6	Correct	45 ms	5792 KB	Output is correct
7	Correct	67 ms	5792 KB	Output is correct
8	Correct	44 ms	5844 KB	Output is correct
9	Incorrect	55 ms	7804 KB	Output isn't correct
10	Incorrect	56 ms	7804 KB	Output isn't correct
11	Incorrect	56 ms	7804 KB	Output isn't correct
12	Incorrect	117 ms	7804 KB	Output isn't correct
13	Incorrect	170 ms	8532 KB	Output isn't correct
14	Incorrect	324 ms	9996 KB	Output isn't correct
15	Incorrect	256 ms	9996 KB	Output isn't correct
16	Incorrect	438 ms	11564 KB	Output isn't correct
17	Incorrect	603 ms	15020 KB	Output isn't correct
18	Incorrect	472 ms	15020 KB	Output isn't correct
19	Incorrect	583 ms	20420 KB	Output isn't correct
20	Incorrect	514 ms	20420 KB	Output isn't correct