oj.uz

Submission #999218

# Submission time Handle Problem Language Result Execution time Memory
999218 2024-06-15T08:18:57 Z 8pete8 Road Construction (JOI21_road_construction) C++17
59 / 100
 3024 ms 2097152 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{
    pii val;
    node*l,*r;
    node():val({inf,inf}),l(0),r(0){};
};
map<int,vector<int>>mp;
map<int,int>cnt[mxn+10];
struct persist{
    node *root[mxn+10];
    pii get(node *x){return (x==NULL)?make_pair(inf,inf):x->val;}
    void update(int l,int r,node *last,node *&cur,int pos,int val){
        if(last==NULL)cur=new node();
        else cur=new node(*last);
        if(l==r)return void(cur->val={val,pos});
        int mid=l+(r-l)/2;
        if(pos<=mid)update(l,mid,((last==NULL)?last:last->l),cur->l,pos,val);
        else update(mid+1,r,((last==NULL)?last:last->r),cur->r,pos,val);
        cur->val=min(get(cur->l),get(cur->r));
    }
    pii qry(int l,int r,node *cur,int ql,int qr){
        if(cur==NULL||l>qr||r<ql)return {inf,inf};
        if(ql<=l&&r<=qr)return cur->val;
        int mid=l+(r-l)/2;
        return min(qry(l,mid,cur->l,ql,qr),qry(mid+1,r,cur->r,ql,qr));
    }
}t,t2;
void show(){
    cout<<"PPPP\n";
    for(int i=6;i<7;i++){
        for(int j=3;j<=3;j++)cout<<t.qry(nx,mx,t.root[i],j,j).f<<" ";
        cout<<'\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);
        t2.update(nx,mx,t2.root[i-(i!=0)],t2.root[i],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),b=t2.qry(nx,mx,t2.root[x],nx,v[x].s-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);
                t2.update(nx,mx,t2.root[x],t2.root[x],a.s,-up-a.s);
            }
            else t.update(nx,mx,t.root[x],t.root[x],a.s,inf),t2.update(nx,mx,t2.root[x],t2.root[x],a.s,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);
                t2.update(nx,mx,t2.root[x],t2.root[x],b.s,-up-b.s);
            }
            else t.update(nx,mx,t.root[x],t.root[x],b.s,inf),t2.update(nx,mx,t2.root[x],t2.root[x],b.s,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}),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;}
      |                    ^
road_construction.cpp:52:66: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   52 |     void update(int l,int r,node *last,node *&cur,int pos,int val){
      |                                                                  ^
road_construction.cpp:61:48: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   61 |     pii qry(int l,int r,node *cur,int ql,int qr){
      |                                                ^
road_construction.cpp:68:11: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   68 | void show(){
      |           ^
road_construction.cpp:75:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   75 | int32_t main(){
      |              ^
road_construction.cpp: In function 'int32_t main()':
road_construction.cpp:87:31: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   87 |     auto del=[&](int x,int pos){
      |                               ^
road_construction.cpp:92:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   92 |     auto get=[&](int x){
      |                       ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1265 ms 788212 KB Output is correct
2 Correct 1384 ms 788304 KB Output is correct
3 Correct 1260 ms 784980 KB Output is correct
4 Correct 1047 ms 775416 KB Output is correct
5 Correct 1294 ms 786256 KB Output is correct
6 Correct 15 ms 26072 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 2142 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2482 ms 1566220 KB Output is correct
2 Correct 2418 ms 1566656 KB Output is correct
3 Correct 2 ms 13912 KB Output is correct
4 Correct 1255 ms 1497380 KB Output is correct
5 Correct 1479 ms 1541048 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2482 ms 1566220 KB Output is correct
2 Correct 2418 ms 1566656 KB Output is correct
3 Correct 2 ms 13912 KB Output is correct
4 Correct 1255 ms 1497380 KB Output is correct
5 Correct 1479 ms 1541048 KB Output is correct
6 Correct 2428 ms 1566480 KB Output is correct
7 Correct 2451 ms 1566468 KB Output is correct
8 Correct 2 ms 13912 KB Output is correct
9 Correct 2 ms 13916 KB Output is correct
10 Correct 2595 ms 1563504 KB Output is correct
11 Correct 1362 ms 1497508 KB Output is correct
12 Correct 1596 ms 1541052 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1265 ms 788212 KB Output is correct
2 Correct 1384 ms 788304 KB Output is correct
3 Correct 1260 ms 784980 KB Output is correct
4 Correct 1047 ms 775416 KB Output is correct
5 Correct 1294 ms 786256 KB Output is correct
6 Correct 15 ms 26072 KB Output is correct
7 Correct 2998 ms 1404456 KB Output is correct
8 Correct 3024 ms 1404456 KB Output is correct
9 Correct 1159 ms 774868 KB Output is correct
10 Correct 2242 ms 1401028 KB Output is correct
11 Correct 2400 ms 1400372 KB Output is correct
12 Correct 1565 ms 1394628 KB Output is correct
13 Correct 1614 ms 1389000 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1265 ms 788212 KB Output is correct
2 Correct 1384 ms 788304 KB Output is correct
3 Correct 1260 ms 784980 KB Output is correct
4 Correct 1047 ms 775416 KB Output is correct
5 Correct 1294 ms 786256 KB Output is correct
6 Correct 15 ms 26072 KB Output is correct
7 Runtime error 2142 ms 2097152 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -