oj.uz

Submission #295071

# Submission time Handle Problem Language Result Execution time Memory
295071 2020-09-09T13:06:15 Z 문홍윤(#5821) Treatment Project (JOI20_treatment) C++17
4 / 100
 459 ms 43096 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define eb emplace_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(all(x))
#define press(x) x.erase(unique(all(x)), x.end());
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;

int n, m;
bool ch[100010];
pair<pii, pil> arr[100010];
vector<int> id;

struct FENWICK{
    vector<pli> tree[100010];
    vector<int> sum(int i, LL lim){
        vector<int> ret;
        for(; i; i-=(i&-i)){
            while(tree[i].size()){
                pli nw=tree[i].back();
                if(nw.F>lim)break;
                ret.eb(nw.S);
                tree[i].pop_back();
            }
        }
        return ret;
    }
    void update(int i, pli num){
        for(; i<=100000; i+=(i&-i))tree[i].eb(num);
    }
}fen;

priority_queue<pli, vector<pli>, greater<pli> > pq;
bool cmp(pair<pii, pil> a, pair<pii, pil> b){
    return a.F.F+a.S.F>b.F.F+b.S.F;
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=m; i++){
        scanf("%d %d %d %lld", &arr[i].F.F, &arr[i].F.S, &arr[i].S.F, &arr[i].S.S);
        id.eb(arr[i].F.S-arr[i].F.F);
    }
    svec(id); press(id);
    sort(arr+1, arr+m+1, cmp);
    for(int i=1; i<=m; i++){
        if(arr[i].F.S==1){
            ch[i]=true;
            pq.push(mp(arr[i].S.S, i));
        }
        int num=lower_bound(all(id), arr[i].F.S-arr[i].F.F)-id.begin()+1;
        fen.update(num, mp(arr[i].F.F+arr[i].F.S, i));
    }
    while(pq.size()){
        LL d=pq.top().F; int nw=pq.top().S;
        pq.pop();
        if(arr[nw].S.F==n)return !printf("%lld", d);
        int num=upper_bound(all(id), arr[nw].S.F-arr[nw].F.F+1)-id.begin();
        vector<int> vc=fen.sum(num, arr[nw].F.F+arr[nw].S.F+1);
        for(auto i:vc){
            ch[i]=true;
            pq.push(mp(d+arr[i].S.S, i));
        }
    }
    printf("-1");
}

Compilation message

treatment.cpp: In function 'int main()':
treatment.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
treatment.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |         scanf("%d %d %d %lld", &arr[i].F.F, &arr[i].F.S, &arr[i].S.F, &arr[i].S.S);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 26092 KB Output is correct
2 Correct 219 ms 25056 KB Output is correct
3 Correct 459 ms 39148 KB Output is correct
4 Correct 449 ms 39392 KB Output is correct
5 Correct 137 ms 39536 KB Output is correct
6 Correct 242 ms 32476 KB Output is correct
7 Correct 299 ms 32856 KB Output is correct
8 Correct 103 ms 30816 KB Output is correct
9 Correct 111 ms 29332 KB Output is correct
10 Correct 154 ms 29400 KB Output is correct
11 Correct 194 ms 28004 KB Output is correct
12 Correct 182 ms 30948 KB Output is correct
13 Correct 336 ms 43096 KB Output is correct
14 Correct 317 ms 43092 KB Output is correct
15 Correct 397 ms 28056 KB Output is correct
16 Correct 402 ms 28100 KB Output is correct
17 Correct 335 ms 27112 KB Output is correct
18 Correct 161 ms 28004 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 3 ms 2664 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2720 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 3 ms 2688 KB Output is correct
12 Incorrect 2 ms 2688 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 3 ms 2664 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2720 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 3 ms 2688 KB Output is correct
12 Incorrect 2 ms 2688 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 26092 KB Output is correct
2 Correct 219 ms 25056 KB Output is correct
3 Correct 459 ms 39148 KB Output is correct
4 Correct 449 ms 39392 KB Output is correct
5 Correct 137 ms 39536 KB Output is correct
6 Correct 242 ms 32476 KB Output is correct
7 Correct 299 ms 32856 KB Output is correct
8 Correct 103 ms 30816 KB Output is correct
9 Correct 111 ms 29332 KB Output is correct
10 Correct 154 ms 29400 KB Output is correct
11 Correct 194 ms 28004 KB Output is correct
12 Correct 182 ms 30948 KB Output is correct
13 Correct 336 ms 43096 KB Output is correct
14 Correct 317 ms 43092 KB Output is correct
15 Correct 397 ms 28056 KB Output is correct
16 Correct 402 ms 28100 KB Output is correct
17 Correct 335 ms 27112 KB Output is correct
18 Correct 161 ms 28004 KB Output is correct
19 Correct 2 ms 2688 KB Output is correct
20 Correct 3 ms 2688 KB Output is correct
21 Correct 3 ms 2688 KB Output is correct
22 Correct 3 ms 2664 KB Output is correct
23 Correct 2 ms 2688 KB Output is correct
24 Correct 2 ms 2688 KB Output is correct
25 Correct 2 ms 2720 KB Output is correct
26 Correct 2 ms 2688 KB Output is correct
27 Correct 2 ms 2688 KB Output is correct
28 Correct 2 ms 2688 KB Output is correct
29 Correct 3 ms 2688 KB Output is correct
30 Incorrect 2 ms 2688 KB Output isn't correct
31 Halted 0 ms 0 KB -