oj.uz

답안 #934137

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
934137 2024-02-26T21:04:21 Z velislavgarkov Event Hopping 2 (JOI21_event2) C++14
32 / 100
 66 ms 46320 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_map>
using namespace std;
const int MAXN=1e5+10;
#define endl '\n'
struct Range {
    int l, r;
    int ind;
    bool friend operator < (Range a, Range b) {
        return a.r<b.r;
    }
};
struct Hole {
    int l, r, res;
    bool friend operator < (Hole a, Hole b) {
        return a.r<b.r;
    }
};
Range e[MAXN], og[MAXN];
int points[2*MAXN];
unordered_map <int,int> um;
vector <int> ans;
set <Hole> s;
int sp[2][MAXN][20], cnt;
int n, k;
void sparce_table() {
    for (int i=1;(1<<i)<=n;i++) {
        for (int j=1;j+(1<<i)-1<=n;j++) {
            sp[0][j][i]=max(sp[0][j][i-1], sp[0][j + (1 << (i-1))][i-1]);
        }
    }
}
void sparce_tree() {
    for (int i=1;(1<<i)<=cnt;i++) {
        for (int j=0;j<=cnt;j++) {
            if (sp[1][j][i-1]==0) continue;
            sp[1][j][i]=sp[1][sp[1][j][i-1]][i-1];
        }
    }
}
int find_dist(int cur, int gr) {
    int st=18, res=0;
    while (st>=0) {
        if (sp[1][cur][st]!=0 && sp[1][cur][st]<=gr) {
            cur=sp[1][cur][st];
            res+=(1<<st);
        }
        st--;
    }
    return res;
}
int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    for (int i=1;i<=n;i++) {
        cin >> e[i].l >> e[i].r;
        e[i].ind=i;
        points[2*i-1]=e[i].l;
        points[2*i]=e[i].r;
    }
    sort(points+1,points+2*n+1);
    cnt=1;
    for (int i=1;i<=2*n;i++) {
        if (um[points[i]]!=0) continue;
        um[points[i]]=cnt;
        cnt++;
    }
    for (int i=1;i<=n;i++) {
        e[i].l=um[e[i].l];
        e[i].r=um[e[i].r];
        og[i]=e[i];
    }
    sort(e+1,e+n+1);
    for (int i=1;i<=n;i++) sp[0][i][0]=e[i].l;
    sparce_table();
    for (int i=n-1;i>=1;i--) {
        if (e[i].r==e[i+1].r) continue;
        int st=18, j=i+1;
        if (e[j].l<e[i].r) {
            while (st>=0) {
                if (j+(1<<st)-1<=n && sp[0][j][st]<e[i].r) j+=(1<<st);
                st--;
            }
        }
        sp[1][e[i].r][0]=e[j].r;
    }
    sp[1][0][0]=e[1].r;
    sparce_tree();
    s.insert({0,cnt+1,k});
    int cur_sum=k;
    for (int i=1;i<=n;i++) {
        auto it=s.lower_bound({og[i].r,og[i].r,1});
        if ((*it).l>og[i].l) continue;
        int curl, curr;
        curl=(*it).l; curr=(*it).r;
        int lef=find_dist(curl,og[i].l);
        int ri=find_dist(og[i].r,curr);
        if (lef+ri+1+cur_sum-(*it).res>=k) {
            cur_sum-=(*it).res;
            cur_sum+=lef+ri+1;
            ans.push_back(i);
            s.erase(it);
            s.insert({curl,og[i].l,lef});
            s.insert({og[i].r,curr,ri});
        }
        if (ans.size()==k) break;
    }
    if (ans.size()<k) cout << -1 << endl;
    else for (auto i:ans) cout << i << endl;
    return 0;
}
/*
5 4
1 3
2 5
8 9
6 8
10 15
*/

Compilation message

event2.cpp: In function 'int main()':
event2.cpp:110:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  110 |         if (ans.size()==k) break;
      |             ~~~~~~~~~~^~~
event2.cpp:112:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  112 |     if (ans.size()<k) cout << -1 << endl;
      |         ~~~~~~~~~~^~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Runtime error 66 ms 46320 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6608 KB Output is correct
9 Correct 1 ms 6584 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6488 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 2 ms 6492 KB Output is correct
22 Correct 1 ms 6488 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 1 ms 6488 KB Output is correct
25 Correct 1 ms 6488 KB Output is correct
26 Correct 1 ms 6492 KB Output is correct
27 Correct 1 ms 6492 KB Output is correct

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6608 KB Output is correct
9 Correct 1 ms 6584 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6488 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 2 ms 6492 KB Output is correct
22 Correct 1 ms 6488 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 1 ms 6488 KB Output is correct
25 Correct 1 ms 6488 KB Output is correct
26 Correct 1 ms 6492 KB Output is correct
27 Correct 1 ms 6492 KB Output is correct
28 Correct 3 ms 9048 KB Output is correct
29 Correct 3 ms 9052 KB Output is correct
30 Correct 3 ms 9304 KB Output is correct
31 Correct 3 ms 9052 KB Output is correct
32 Correct 3 ms 9052 KB Output is correct
33 Correct 4 ms 9052 KB Output is correct
34 Correct 4 ms 8980 KB Output is correct
35 Correct 5 ms 9308 KB Output is correct
36 Correct 4 ms 9308 KB Output is correct
37 Correct 4 ms 9308 KB Output is correct
38 Correct 3 ms 9172 KB Output is correct
39 Correct 4 ms 9308 KB Output is correct
40 Correct 4 ms 9308 KB Output is correct
41 Correct 4 ms 9308 KB Output is correct
42 Correct 4 ms 9052 KB Output is correct
43 Correct 4 ms 9052 KB Output is correct
44 Correct 4 ms 9236 KB Output is correct
45 Correct 3 ms 9240 KB Output is correct
46 Correct 4 ms 9052 KB Output is correct
47 Correct 3 ms 8924 KB Output is correct
48 Correct 4 ms 9052 KB Output is correct
49 Correct 4 ms 9052 KB Output is correct
50 Correct 4 ms 9052 KB Output is correct
51 Correct 3 ms 9048 KB Output is correct
52 Correct 3 ms 9052 KB Output is correct
53 Correct 3 ms 9052 KB Output is correct
54 Correct 4 ms 8964 KB Output is correct
55 Correct 3 ms 9052 KB Output is correct
56 Correct 3 ms 9184 KB Output is correct
57 Correct 3 ms 9052 KB Output is correct
58 Correct 4 ms 9052 KB Output is correct
59 Correct 3 ms 9052 KB Output is correct
60 Correct 3 ms 9032 KB Output is correct
61 Correct 3 ms 9052 KB Output is correct
62 Correct 3 ms 8972 KB Output is correct
63 Correct 3 ms 9052 KB Output is correct
64 Correct 3 ms 8796 KB Output is correct

Subtask #4
0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Runtime error 66 ms 46320 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -