oj.uz

Submission #999243

# Submission time Handle Problem Language Result Execution time Memory
999243 2024-06-15T08:37:50 Z 8pete8 Road Construction (JOI21_road_construction) C++17
100 / 100
 3303 ms 1574332 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
persist is alrdy sparse?
*/
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;
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++)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:46:10: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   46 |     node():val({{inf,inf},{inf,inf}}),l(0),r(0){};
      |          ^
road_construction.cpp:52:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   52 |     pii get(node *x){return (x==NULL)?make_pair(inf,inf):x->val.f;}
      |                    ^
road_construction.cpp:53:21: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   53 |     pii get2(node *x){return (x==NULL)?make_pair(inf,inf):x->val.s;}
      |                     ^
road_construction.cpp:54:75: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   54 |     void update(int l,int r,node *last,node *&cur,int pos,int val,int val2){
      |                                                                           ^
road_construction.cpp:66:57: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   66 |     pii qry(int l,int r,node *cur,int ql,int qr,int mode){
      |                                                         ^
road_construction.cpp:76:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   76 | int32_t main(){
      |              ^
road_construction.cpp: In function 'int32_t main()':
road_construction.cpp:84:31: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   84 |     auto del=[&](int x,int pos){
      |                               ^
road_construction.cpp:89:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   89 |     auto get=[&](int x){
      |                       ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 971 ms 532332 KB Output is correct
2 Correct 984 ms 532304 KB Output is correct
3 Correct 903 ms 530244 KB Output is correct
4 Correct 716 ms 523232 KB Output is correct
5 Correct 909 ms 530632 KB Output is correct
6 Correct 16 ms 22108 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1502 ms 1491836 KB Output is correct
2 Correct 1542 ms 1491652 KB Output is correct
3 Correct 480 ms 502352 KB Output is correct
4 Correct 1369 ms 1491552 KB Output is correct
5 Correct 1528 ms 1492080 KB Output is correct
6 Correct 1462 ms 1491720 KB Output is correct
7 Correct 1522 ms 1491048 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2017 ms 1060600 KB Output is correct
2 Correct 1804 ms 1060604 KB Output is correct
3 Correct 2 ms 13916 KB Output is correct
4 Correct 881 ms 1005260 KB Output is correct
5 Correct 1124 ms 1034116 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2017 ms 1060600 KB Output is correct
2 Correct 1804 ms 1060604 KB Output is correct
3 Correct 2 ms 13916 KB Output is correct
4 Correct 881 ms 1005260 KB Output is correct
5 Correct 1124 ms 1034116 KB Output is correct
6 Correct 2008 ms 1060648 KB Output is correct
7 Correct 1955 ms 1060656 KB Output is correct
8 Correct 2 ms 13912 KB Output is correct
9 Correct 2 ms 13912 KB Output is correct
10 Correct 1693 ms 1057348 KB Output is correct
11 Correct 861 ms 1005252 KB Output is correct
12 Correct 999 ms 1034100 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 971 ms 532332 KB Output is correct
2 Correct 984 ms 532304 KB Output is correct
3 Correct 903 ms 530244 KB Output is correct
4 Correct 716 ms 523232 KB Output is correct
5 Correct 909 ms 530632 KB Output is correct
6 Correct 16 ms 22108 KB Output is correct
7 Correct 1923 ms 946364 KB Output is correct
8 Correct 1985 ms 946248 KB Output is correct
9 Correct 777 ms 523092 KB Output is correct
10 Correct 1628 ms 943040 KB Output is correct
11 Correct 1726 ms 942276 KB Output is correct
12 Correct 1124 ms 935876 KB Output is correct
13 Correct 1344 ms 931528 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 971 ms 532332 KB Output is correct
2 Correct 984 ms 532304 KB Output is correct
3 Correct 903 ms 530244 KB Output is correct
4 Correct 716 ms 523232 KB Output is correct
5 Correct 909 ms 530632 KB Output is correct
6 Correct 16 ms 22108 KB Output is correct
7 Correct 1502 ms 1491836 KB Output is correct
8 Correct 1542 ms 1491652 KB Output is correct
9 Correct 480 ms 502352 KB Output is correct
10 Correct 1369 ms 1491552 KB Output is correct
11 Correct 1528 ms 1492080 KB Output is correct
12 Correct 1462 ms 1491720 KB Output is correct
13 Correct 1522 ms 1491048 KB Output is correct
14 Correct 2017 ms 1060600 KB Output is correct
15 Correct 1804 ms 1060604 KB Output is correct
16 Correct 2 ms 13916 KB Output is correct
17 Correct 881 ms 1005260 KB Output is correct
18 Correct 1124 ms 1034116 KB Output is correct
19 Correct 2008 ms 1060648 KB Output is correct
20 Correct 1955 ms 1060656 KB Output is correct
21 Correct 2 ms 13912 KB Output is correct
22 Correct 2 ms 13912 KB Output is correct
23 Correct 1693 ms 1057348 KB Output is correct
24 Correct 861 ms 1005252 KB Output is correct
25 Correct 999 ms 1034100 KB Output is correct
26 Correct 1923 ms 946364 KB Output is correct
27 Correct 1985 ms 946248 KB Output is correct
28 Correct 777 ms 523092 KB Output is correct
29 Correct 1628 ms 943040 KB Output is correct
30 Correct 1726 ms 942276 KB Output is correct
31 Correct 1124 ms 935876 KB Output is correct
32 Correct 1344 ms 931528 KB Output is correct
33 Correct 3277 ms 1574332 KB Output is correct
34 Correct 3303 ms 1574120 KB Output is correct
35 Correct 2614 ms 1563580 KB Output is correct
36 Correct 1680 ms 1547516 KB Output is correct
37 Correct 1633 ms 1548340 KB Output is correct
38 Correct 1847 ms 1547028 KB Output is correct