oj.uz

Submission #921804

# Submission time Handle Problem Language Result Execution time Memory
921804 2024-02-04T10:37:07 Z browntoad Road Construction (JOI21_road_construction) C++14
33 / 100
 6854 ms 124616 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 (L == R) break;
        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

# Verdict Execution time Memory Grader output
1 Correct 101 ms 30620 KB Output is correct
2 Correct 102 ms 30656 KB Output is correct
3 Correct 87 ms 30744 KB Output is correct
4 Correct 81 ms 30836 KB Output is correct
5 Incorrect 95 ms 29576 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2138 ms 121060 KB Output is correct
2 Correct 2130 ms 124096 KB Output is correct
3 Correct 72 ms 30656 KB Output is correct
4 Correct 2104 ms 124120 KB Output is correct
5 Correct 2050 ms 124020 KB Output is correct
6 Correct 1996 ms 124616 KB Output is correct
7 Correct 1701 ms 123440 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4988 ms 118080 KB Output is correct
2 Correct 6272 ms 118080 KB Output is correct
3 Correct 8 ms 23896 KB Output is correct
4 Correct 1772 ms 118204 KB Output is correct
5 Correct 1386 ms 116416 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4988 ms 118080 KB Output is correct
2 Correct 6272 ms 118080 KB Output is correct
3 Correct 8 ms 23896 KB Output is correct
4 Correct 1772 ms 118204 KB Output is correct
5 Correct 1386 ms 116416 KB Output is correct
6 Correct 6595 ms 118188 KB Output is correct
7 Correct 6450 ms 118088 KB Output is correct
8 Correct 9 ms 24112 KB Output is correct
9 Correct 8 ms 23900 KB Output is correct
10 Correct 6854 ms 117888 KB Output is correct
11 Correct 1328 ms 117896 KB Output is correct
12 Correct 1682 ms 116328 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 30620 KB Output is correct
2 Correct 102 ms 30656 KB Output is correct
3 Correct 87 ms 30744 KB Output is correct
4 Correct 81 ms 30836 KB Output is correct
5 Incorrect 95 ms 29576 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 30620 KB Output is correct
2 Correct 102 ms 30656 KB Output is correct
3 Correct 87 ms 30744 KB Output is correct
4 Correct 81 ms 30836 KB Output is correct
5 Incorrect 95 ms 29576 KB Output isn't correct
6 Halted 0 ms 0 KB -