oj.uz

Submission #999237

# Submission time Handle Problem Language Result Execution time Memory
999237 2024-06-15T08:35:01 Z 8pete8 Road Construction (JOI21_road_construction) C++17
100 / 100
 3148 ms 1579452 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
using namespace std;
const int mxn=2e5+5e4+10,inf=1e18,lg=30,mx=1e9,nx=-1e9,minf=-1e18,mod=998244353;
/*
find k cheapest road
we can get the cheapest road for i node with sparse seg?
persist sparse segtee ??TT
*/
int n,k;
struct node{
    pair<pii,pii> val;
    node*l,*r;
    node():val({{inf,inf},{inf,inf}}),l(0),r(0){};
};
map<int32_t,vector<int32_t>>mp;
map<int32_t,int32_t>cnt[mxn+10];
struct persist{
    node *root[mxn+10];
    pii get(node *x){return (x==NULL)?make_pair(inf,inf):x->val.f;}
    pii get2(node *x){return (x==NULL)?make_pair(inf,inf):x->val.s;}
    void update(int l,int r,node *last,node *&cur,int pos,int val,int val2){
        if(last==NULL)cur=new node();
        else cur=new node(*last);
        if(l==r){
            return void(cur->val={{val,pos},{val2,pos}});
        }
        int mid=l+(r-l)/2;
        if(pos<=mid)update(l,mid,((last==NULL)?last:last->l),cur->l,pos,val,val2);
        else update(mid+1,r,((last==NULL)?last:last->r),cur->r,pos,val,val2);
        cur->val.f=min(get(cur->l),get(cur->r));
        cur->val.s=min(get2(cur->l),get2(cur->r));
    }
    pii qry(int l,int r,node *cur,int ql,int qr,int mode){
        if(cur==NULL||l>qr||r<ql)return {inf,inf};
        if(ql<=l&&r<=qr){
            if(mode)return cur->val.s;
            return cur->val.f;
        }
        int mid=l+(r-l)/2;
        return min(qry(l,mid,cur->l,ql,qr,mode),qry(mid+1,r,cur->r,ql,qr,mode));
    }
}t,t2;
void show(){
    cout<<"PPPP\n";
}
int32_t main(){
    fastio
    cin>>n>>k;
    vector<pii>v(n);
    for(int i=0;i<n;i++)cin>>v[i].f>>v[i].s;
    sort(all(v));
    for(int i=0;i<n;i++)mp[v[i].s].pb(i);
    for(int i=1;i<n;i++){
        //update the last one
        t.update(nx,mx,t.root[i-(i!=0)],t.root[i],v[i-1].s,-v[i-1].f+v[i-1].s,-v[i-1].f-v[i-1].s);
    }
    auto del=[&](int x,int pos){
        if(cnt[x].find(pos)==cnt[x].end())cnt[x][pos]=upper_bound(all(mp[pos]),x-1)-mp[pos].begin()-1;
        cnt[x][pos]--;
        return ((cnt[x][pos]<0)?inf:v[mp[pos][cnt[x][pos]]].f);
    };
    auto get=[&](int x){
        pii a=t.qry(nx,mx,t.root[x],v[x].s,mx,0),b=t.qry(nx,mx,t.root[x],nx,v[x].s-1,1);
        int up;
        if(max(minf,a.f-v[x].s)<min(inf,b.f+v[x].s)){
            if(a.s==inf)return inf;
            up=del(x,a.s);
            if(up!=inf)t.update(nx,mx,t.root[x],t.root[x],a.s,-up+a.s,-up-a.s);
            else t.update(nx,mx,t.root[x],t.root[x],a.s,inf,inf);
            return v[x].f+a.f-v[x].s;
        }
        else{
            if(b.s==inf)return inf;
            up=del(x,b.s);
            if(up!=inf)t.update(nx,mx,t.root[x],t.root[x],b.s,-up+b.s,-up-b.s);
            else t.update(nx,mx,t.root[x],t.root[x],b.s,inf,inf);
            return v[x].f+b.f+v[x].s;
        }
    };
    priority_queue<pii,vector<pii>,greater<pii>>pq;
    for(int i=0;i<n;i++)pq.push({get(i),i});
    for(int i=0;i<k;i++){
        if(pq.empty())assert(0);
        cout<<pq.top().f<<"\n";
        int x=pq.top().s;
        pq.pop();
        pq.push({get(x),x});
    }
}
/*
3 3
-1 0
0 2
0 0

5 4 
1 -1 
2 0 
-1 0 
0 2 
0 -2

4 6 
0 0 
1 0 
3 0
4 0
*/

Compilation message

road_construction.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
road_construction.cpp:45:10: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   45 |     node():val({{inf,inf},{inf,inf}}),l(0),r(0){};
      |          ^
road_construction.cpp:51:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   51 |     pii get(node *x){return (x==NULL)?make_pair(inf,inf):x->val.f;}
      |                    ^
road_construction.cpp:52:21: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   52 |     pii get2(node *x){return (x==NULL)?make_pair(inf,inf):x->val.s;}
      |                     ^
road_construction.cpp:53:75: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   53 |     void update(int l,int r,node *last,node *&cur,int pos,int val,int val2){
      |                                                                           ^
road_construction.cpp:65:57: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   65 |     pii qry(int l,int r,node *cur,int ql,int qr,int mode){
      |                                                         ^
road_construction.cpp:75:11: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   75 | void show(){
      |           ^
road_construction.cpp:78:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   78 | int32_t main(){
      |              ^
road_construction.cpp: In function 'int32_t main()':
road_construction.cpp:89:31: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   89 |     auto del=[&](int x,int pos){
      |                               ^
road_construction.cpp:94:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   94 |     auto get=[&](int x){
      |                       ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 899 ms 532128 KB Output is correct
2 Correct 885 ms 532308 KB Output is correct
3 Correct 880 ms 529976 KB Output is correct
4 Correct 721 ms 523088 KB Output is correct
5 Correct 894 ms 530776 KB Output is correct
6 Correct 10 ms 22108 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1503 ms 1491800 KB Output is correct
2 Correct 1520 ms 1494724 KB Output is correct
3 Correct 480 ms 502356 KB Output is correct
4 Correct 1356 ms 1494728 KB Output is correct
5 Correct 1260 ms 1494688 KB Output is correct
6 Correct 1232 ms 1494920 KB Output is correct
7 Correct 1320 ms 1494212 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1673 ms 1060800 KB Output is correct
2 Correct 1619 ms 1060584 KB Output is correct
3 Correct 2 ms 13916 KB Output is correct
4 Correct 791 ms 1005308 KB Output is correct
5 Correct 947 ms 1034432 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1673 ms 1060800 KB Output is correct
2 Correct 1619 ms 1060584 KB Output is correct
3 Correct 2 ms 13916 KB Output is correct
4 Correct 791 ms 1005308 KB Output is correct
5 Correct 947 ms 1034432 KB Output is correct
6 Correct 1735 ms 1060692 KB Output is correct
7 Correct 1773 ms 1060544 KB Output is correct
8 Correct 3 ms 13916 KB Output is correct
9 Correct 2 ms 13916 KB Output is correct
10 Correct 1557 ms 1057468 KB Output is correct
11 Correct 774 ms 1005344 KB Output is correct
12 Correct 957 ms 1034432 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 899 ms 532128 KB Output is correct
2 Correct 885 ms 532308 KB Output is correct
3 Correct 880 ms 529976 KB Output is correct
4 Correct 721 ms 523088 KB Output is correct
5 Correct 894 ms 530776 KB Output is correct
6 Correct 10 ms 22108 KB Output is correct
7 Correct 1906 ms 946372 KB Output is correct
8 Correct 1944 ms 946116 KB Output is correct
9 Correct 756 ms 522864 KB Output is correct
10 Correct 1562 ms 943044 KB Output is correct
11 Correct 1664 ms 942620 KB Output is correct
12 Correct 1034 ms 935916 KB Output is correct
13 Correct 1136 ms 931520 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 899 ms 532128 KB Output is correct
2 Correct 885 ms 532308 KB Output is correct
3 Correct 880 ms 529976 KB Output is correct
4 Correct 721 ms 523088 KB Output is correct
5 Correct 894 ms 530776 KB Output is correct
6 Correct 10 ms 22108 KB Output is correct
7 Correct 1503 ms 1491800 KB Output is correct
8 Correct 1520 ms 1494724 KB Output is correct
9 Correct 480 ms 502356 KB Output is correct
10 Correct 1356 ms 1494728 KB Output is correct
11 Correct 1260 ms 1494688 KB Output is correct
12 Correct 1232 ms 1494920 KB Output is correct
13 Correct 1320 ms 1494212 KB Output is correct
14 Correct 1673 ms 1060800 KB Output is correct
15 Correct 1619 ms 1060584 KB Output is correct
16 Correct 2 ms 13916 KB Output is correct
17 Correct 791 ms 1005308 KB Output is correct
18 Correct 947 ms 1034432 KB Output is correct
19 Correct 1735 ms 1060692 KB Output is correct
20 Correct 1773 ms 1060544 KB Output is correct
21 Correct 3 ms 13916 KB Output is correct
22 Correct 2 ms 13916 KB Output is correct
23 Correct 1557 ms 1057468 KB Output is correct
24 Correct 774 ms 1005344 KB Output is correct
25 Correct 957 ms 1034432 KB Output is correct
26 Correct 1906 ms 946372 KB Output is correct
27 Correct 1944 ms 946116 KB Output is correct
28 Correct 756 ms 522864 KB Output is correct
29 Correct 1562 ms 943044 KB Output is correct
30 Correct 1664 ms 942620 KB Output is correct
31 Correct 1034 ms 935916 KB Output is correct
32 Correct 1136 ms 931520 KB Output is correct
33 Correct 3091 ms 1579452 KB Output is correct
34 Correct 3148 ms 1579196 KB Output is correct
35 Correct 2643 ms 1568580 KB Output is correct
36 Correct 1720 ms 1552864 KB Output is correct
37 Correct 1727 ms 1553604 KB Output is correct
38 Correct 1851 ms 1552396 KB Output is correct