oj.uz

Submission #415564

# Submission time Handle Problem Language Result Execution time Memory
415564 2021-06-01T08:42:16 Z 조영욱(#7635) Road Construction (JOI21_road_construction) C++17
27 / 100
 8784 ms 259892 KB 
#include <bits/stdc++.h>
using namespace std;

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

struct Node {
    vector<long long> v;
};

Node merge(Node l,Node r) {
    Node ret;
    int lind=0;
    int rind=0;
    for(int i=0;i<10;i++) {
        if (l.v[lind]<r.v[rind]) {
            ret.v.push_back(l.v[lind++]);
        }
        else {
            ret.v.push_back(r.v[rind++]);
        }
    }
    return ret;
}

Node emp;

struct SegmentTree {
    Node seg[sz*2];
    Node sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
        if (r<nodel||l>noder) {
            return emp;
        }
        if (l<=nodel&&noder<=r) {
            return seg[node];
        }
        int mid=(nodel+noder)/2;
        return merge(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;
        Node cpy=emp;
        cpy.v[0]=val;
        seg[i]=merge(seg[i],cpy);
        while (i>1) {
            i/=2;
            seg[i]=merge(seg[i*2],seg[i*2+1]);
        }
    }
};

Node pl(Node a,long long x) {
    for(int i=0;i<10;i++) {
        a.v[i]+=x;
    }
    return a;
}

SegmentTree st1;
SegmentTree st2;

int main(void) {
    int n,k;
    scanf("%d %d",&n,&k);
    for(int i=0;i<10;i++) {
        emp.v.push_back(1e12);
    }
    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]=emp;
        st2.seg[i]=emp;
    }
    Node ret=emp;
    for(int i=0;i<n;i++) {
        int y=lower_bound(press.begin(),press.end(),arr[i].second)-press.begin();
        if (y!=0) {
            ret=merge(ret,pl(st1.sum(0,y-1),arr[i].first+arr[i].second));
        }
        ret=merge(ret,pl(st2.sum(y,sz-1),arr[i].first-arr[i].second));
        st1.update(y,-arr[i].first-arr[i].second);
        st2.update(y,-arr[i].first+arr[i].second);
    }
    for(int i=0;i<k;i++) {
        printf("%lld\n",ret.v[i]);
    }
}

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 261 ms 250612 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 2889 ms 259892 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8244 ms 189920 KB Output is correct
2 Correct 8103 ms 189864 KB Output is correct
3 Correct 154 ms 123312 KB Output is correct
4 Correct 2861 ms 128316 KB Output is correct
5 Correct 5244 ms 128520 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8244 ms 189920 KB Output is correct
2 Correct 8103 ms 189864 KB Output is correct
3 Correct 154 ms 123312 KB Output is correct
4 Correct 2861 ms 128316 KB Output is correct
5 Correct 5244 ms 128520 KB Output is correct
6 Correct 8695 ms 189784 KB Output is correct
7 Correct 8784 ms 189824 KB Output is correct
8 Correct 133 ms 123332 KB Output is correct
9 Correct 132 ms 123344 KB Output is correct
10 Correct 8310 ms 182784 KB Output is correct
11 Correct 2853 ms 128304 KB Output is correct
12 Correct 5231 ms 128436 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 261 ms 250612 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 261 ms 250612 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -