oj.uz

답안 #921800

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
921800 2024-02-04T10:28:29 Z browntoad Road Construction (JOI21_road_construction) C++14
27 / 100
 6472 ms 124092 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast", "unroll-loops")
using namespace std;
#define ll long long
#define int ll
#define FOR(i,a,b) for (int i = (a); i<(b); i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define RREP(i,n) for (int i=(n)-1; i>=0; i--)
#define RREP1(i,n) for (int i=(n); i>=1; i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)(x.size())
#define SQ(x) (x)*(x)
#define pii pair<int, int>
#define pip pair<int, pii>
#define ppi pair<pii, int>
#define pdd pair<double ,double>
#define pcc pair<char, char>
#define endl '\n'
//#define TOAD
#ifdef TOAD
#define bug(x) cerr<<__LINE__<<": "<<#x<<" is "<<x<<endl
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#endif

const ll inf = 1ll<<60;
const int iinf=2147483647;
const ll mod = 998244353;
const ll maxn = 250005;
const ll maxm=15;
const double PI=acos(-1);

ll pw(ll x, ll p, ll m=mod){
    if (p < 0) return 0;
    ll ret=1;
    while (p>0){
        if (p&1){
            ret*=x;
            ret%=m;
        }
        x*=x;
        x%=m;
        p>>=1;
    }
    return ret;
}

ll inv(ll a, ll m=mod){
    return pw(a,m-2,m);
}

int n, k, cur = 0, M;
bool gg = false;
vector<vector<pii>> ord(4*maxn);
vector<pii> vc;
int ans[maxn];

void initO(int l, int r, int x){
    if (l == r){
        ord[x].pb(vc[l]);
        return;
    }
    int mid = l+r>>1;
    initO(l, mid, x+x); initO(mid+1, r, x+x+1);
    int lptr = 0, rptr = 0;
    while(lptr < SZ(ord[x+x]) || rptr < SZ(ord[x+x+1])){
        if (lptr == SZ(ord[x+x])) ord[x].pb(ord[x+x+1][rptr++]);
        else if (rptr == SZ(ord[x+x+1])) ord[x].pb(ord[x+x][lptr++]);
        else if (ord[x+x][lptr].s <= ord[x+x+1][rptr].s) ord[x].pb(ord[x+x][lptr++]);
        else ord[x].pb(ord[x+x+1][rptr++]);
    }

}

void init(){
    cin>>n>>k;
    REP(i, n){
        int x, y; cin>>x>>y;
        vc.pb({x, y});
    }
    sort(ALL(vc));
    initO(0, n-1, 1);
}

void run(int l, int r, int x){
    if (l == r) return;
    if (gg) return;
    int mid = l+r>>1;
    run(l, mid, x+x);
    if (gg) return;
    run(mid+1, r, x+x+1);
    if (gg) return;

    set<int> R;
    int rp = 0;
    pii v;
    REP(i, SZ(ord[x+x])){
        v = ord[x+x][i];
        while(rp < SZ(ord[x+x+1]) && ord[x+x+1][rp].s <= v.s){
            R.insert(-ord[x+x+1][rp].s+ord[x+x+1][rp].f-vc[mid].f);
            rp++;
        }
        if (SZ(R)){
            auto it = R.begin();
            while(it != R.end() && (*it)+v.s+(vc[mid].f-v.f) <= M){
                ans[cur++] = (*it)+v.s+(vc[mid].f-v.f);
                it++;
                if (cur >= k){
                    gg = 1;
                    return;
                }
            }
        }
    }

    R.clear(); rp = SZ(ord[x+x+1])-1;
    RREP(i, SZ(ord[x+x])){
        v = ord[x+x][i];
        while(rp >= 0 && ord[x+x+1][rp].s > v.s){
            R.insert(ord[x+x+1][rp].s+ord[x+x+1][rp].f-vc[mid].f);
            rp--;
        }
        if (SZ(R)){
            auto it = R.begin();
            while(it != R.end() && (*it)-v.s+(vc[mid].f-v.f) <= M){
                ans[cur++] = (*it)-v.s+(vc[mid].f-v.f);
                it++;
                if (cur >= k){
                    gg = 1;
                    return;
                }
            }
        }
    }
}
signed main(){
    IOS();
    init();
    int L = 0, R = 4000000000ll;
    while(L < R){
        M = L+R+1>>1;
        gg = 0;
        cur = 0;
        run(0, n-1, 1);
        if (gg) R = M-1;
        else L = M;
    }
    vector<int> fans;
    REP(i, cur){
        fans.pb(ans[i]);
    }
    while(SZ(fans) < k) fans.pb(L+1);
    sort(ALL(fans));

    REP(i, SZ(fans)){
        cout<<fans[i]<<endl;
    }
    // cout<<L<<endl;
}

Compilation message

road_construction.cpp: In function 'void initO(long long int, long long int, long long int)':
road_construction.cpp:69:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |     int mid = l+r>>1;
      |               ~^~
road_construction.cpp: In function 'void run(long long int, long long int, long long int)':
road_construction.cpp:94:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |     int mid = l+r>>1;
      |               ~^~
road_construction.cpp: In function 'int main()':
road_construction.cpp:147:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  147 |         M = L+R+1>>1;
      |             ~~~^~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 103 ms 30640 KB Output is correct
2 Correct 99 ms 30660 KB Output is correct
3 Correct 98 ms 30776 KB Output is correct
4 Correct 81 ms 30656 KB Output is correct
5 Incorrect 93 ms 29636 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1938 ms 124092 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4440 ms 123164 KB Output is correct
2 Correct 5813 ms 123160 KB Output is correct
3 Correct 8 ms 23900 KB Output is correct
4 Correct 1624 ms 120992 KB Output is correct
5 Correct 1264 ms 121792 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4440 ms 123164 KB Output is correct
2 Correct 5813 ms 123160 KB Output is correct
3 Correct 8 ms 23900 KB Output is correct
4 Correct 1624 ms 120992 KB Output is correct
5 Correct 1264 ms 121792 KB Output is correct
6 Correct 6142 ms 123164 KB Output is correct
7 Correct 6151 ms 123168 KB Output is correct
8 Correct 8 ms 23900 KB Output is correct
9 Correct 8 ms 23896 KB Output is correct
10 Correct 6472 ms 122916 KB Output is correct
11 Correct 1170 ms 121024 KB Output is correct
12 Correct 1498 ms 121852 KB Output is correct

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 103 ms 30640 KB Output is correct
2 Correct 99 ms 30660 KB Output is correct
3 Correct 98 ms 30776 KB Output is correct
4 Correct 81 ms 30656 KB Output is correct
5 Incorrect 93 ms 29636 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 103 ms 30640 KB Output is correct
2 Correct 99 ms 30660 KB Output is correct
3 Correct 98 ms 30776 KB Output is correct
4 Correct 81 ms 30656 KB Output is correct
5 Incorrect 93 ms 29636 KB Output isn't correct
6 Halted 0 ms 0 KB -