Submission #84443

# Submission time Handle Problem Language Result Execution time Memory
84443 2018-11-15T07:57:37 Z someone_aa Job Scheduling (CEOI12_jobs) C++17
40 / 100
584 ms 33792 KB
#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[4*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;
}
# Verdict Execution time Memory Grader output
1 Correct 45 ms 4468 KB Output is correct
2 Correct 47 ms 4784 KB Output is correct
3 Correct 46 ms 5268 KB Output is correct
4 Correct 47 ms 5528 KB Output is correct
5 Correct 47 ms 5848 KB Output is correct
6 Correct 45 ms 6148 KB Output is correct
7 Correct 45 ms 6440 KB Output is correct
8 Correct 72 ms 6732 KB Output is correct
9 Incorrect 54 ms 8972 KB Output isn't correct
10 Incorrect 57 ms 9352 KB Output isn't correct
11 Incorrect 56 ms 9352 KB Output isn't correct
12 Incorrect 117 ms 9352 KB Output isn't correct
13 Incorrect 172 ms 12252 KB Output isn't correct
14 Incorrect 290 ms 15824 KB Output isn't correct
15 Incorrect 248 ms 17556 KB Output isn't correct
16 Incorrect 407 ms 22084 KB Output isn't correct
17 Incorrect 521 ms 28812 KB Output isn't correct
18 Incorrect 467 ms 31464 KB Output isn't correct
19 Runtime error 584 ms 33792 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
20 Runtime error 518 ms 33792 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.