oj.uz

Submission #415536

# Submission time Handle Problem Language Result Execution time Memory
415536 2021-06-01T08:20:19 Z 조영욱(#7635) Road Construction (JOI21_road_construction) C++17
7 / 100
 425 ms 13512 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<long long,long long> P;
P arr[250000];
const int sz=262144;

struct SegmentTree {
    long long seg[sz*2];
    long long sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
        if (r<nodel||l>noder) {
            return 1e12;
        }
        if (l<=nodel&&noder<=r) {
            return seg[node];
        }
        int mid=(nodel+noder)/2;
        return min(sum(l,r,node*2,nodel,mid),sum(l,r,node*2+1,mid+1,noder));
    }

    void update(int i,long long val) {
        i+=sz;
        seg[i]=min(seg[i],val);
        while (i>1) {
            i/=2;
            seg[i]=min(seg[i*2],seg[i*2+1]);
        }
    }
};

SegmentTree st1;
SegmentTree st2;

int main(void) {
    int n,k;
    scanf("%d %d",&n,&k);
    vector<int> press;
    for(int i=0;i<n;i++) {
        scanf("%lld %lld",&arr[i].first,&arr[i].second);
        press.push_back(arr[i].second);
    }
    sort(press.begin(),press.end());
    press.erase(unique(press.begin(),press.end()),press.end());
    sort(arr,arr+n);
    for(int i=0;i<sz*2;i++) {
        st1.seg[i]=1e12;
        st2.seg[i]=1e12;
    }
    long long ret=1e12;
    for(int i=0;i<n;i++) {
        int y=lower_bound(press.begin(),press.end(),arr[i].second)-press.begin();
        if (y!=0) {
            ret=min(ret,arr[i].first+arr[i].second+st1.sum(0,y));
        }
        ret=min(ret,arr[i].first-arr[i].second+st2.sum(y,sz-1));
        st1.update(y,-arr[i].first-arr[i].second);
        st2.update(y,-arr[i].first+arr[i].second);
    }
    printf("%lld",ret);
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf("%d %d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~~
road_construction.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         scanf("%lld %lld",&arr[i].first,&arr[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 8524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 155 ms 13420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 13416 KB Output is correct
2 Correct 411 ms 13512 KB Output is correct
3 Correct 8 ms 8396 KB Output is correct
4 Correct 149 ms 13484 KB Output is correct
5 Correct 220 ms 13436 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 13416 KB Output is correct
2 Correct 411 ms 13512 KB Output is correct
3 Correct 8 ms 8396 KB Output is correct
4 Correct 149 ms 13484 KB Output is correct
5 Correct 220 ms 13436 KB Output is correct
6 Incorrect 413 ms 13460 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 8524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 8524 KB Output isn't correct
2 Halted 0 ms 0 KB -