oj.uz

Submission #999183

# Submission time Handle Problem Language Result Execution time Memory
999183 2024-06-15T07:53:59 Z 8pete8 Road Construction (JOI21_road_construction) C++17
27 / 100
 2147 ms 1550788 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=0;i<n;i++){
        for(int j=0;j<=0;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){
        return inf;
        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[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:93:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   93 |     auto get=[&](int x){
      |                       ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 946 ms 772432 KB Output is correct
2 Correct 964 ms 772432 KB Output is correct
3 Correct 956 ms 769364 KB Output is correct
4 Incorrect 800 ms 761684 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1548 ms 1486052 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2120 ms 1550788 KB Output is correct
2 Correct 2147 ms 1550648 KB Output is correct
3 Correct 2 ms 13916 KB Output is correct
4 Correct 1255 ms 1481700 KB Output is correct
5 Correct 1506 ms 1525252 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2120 ms 1550788 KB Output is correct
2 Correct 2147 ms 1550648 KB Output is correct
3 Correct 2 ms 13916 KB Output is correct
4 Correct 1255 ms 1481700 KB Output is correct
5 Correct 1506 ms 1525252 KB Output is correct
6 Correct 2112 ms 1550780 KB Output is correct
7 Correct 2112 ms 1550776 KB Output is correct
8 Correct 2 ms 13916 KB Output is correct
9 Correct 3 ms 13916 KB Output is correct
10 Correct 2143 ms 1547452 KB Output is correct
11 Correct 1230 ms 1481672 KB Output is correct
12 Correct 1448 ms 1525272 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 946 ms 772432 KB Output is correct
2 Correct 964 ms 772432 KB Output is correct
3 Correct 956 ms 769364 KB Output is correct
4 Incorrect 800 ms 761684 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 946 ms 772432 KB Output is correct
2 Correct 964 ms 772432 KB Output is correct
3 Correct 956 ms 769364 KB Output is correct
4 Incorrect 800 ms 761684 KB Output isn't correct
5 Halted 0 ms 0 KB -