oj.uz

Submission #999167

# Submission time Handle Problem Language Result Execution time Memory
999167 2024-06-15T07:43:59 Z 8pete8 Road Construction (JOI21_road_construction) C++17
27 / 100
 2499 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=3e5+5,inf=1e18,lg=30,mx=1e9,nx=-1e9,minf=-1e9,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,t.root[i]=new node(),t2.root[i]=new node();
    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[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(a.f-v[x].s<b.f+v[x].s){
            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{
            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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1304 ms 791376 KB Output is correct
2 Correct 1352 ms 791380 KB Output is correct
3 Correct 1261 ms 788052 KB Output is correct
4 Incorrect 971 ms 779144 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 2065 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 2458 ms 1593020 KB Output is correct
2 Correct 2499 ms 1597116 KB Output is correct
3 Correct 3 ms 16984 KB Output is correct
4 Correct 1314 ms 1526556 KB Output is correct
5 Correct 1551 ms 1571728 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2458 ms 1593020 KB Output is correct
2 Correct 2499 ms 1597116 KB Output is correct
3 Correct 3 ms 16984 KB Output is correct
4 Correct 1314 ms 1526556 KB Output is correct
5 Correct 1551 ms 1571728 KB Output is correct
6 Correct 2427 ms 1597040 KB Output is correct
7 Correct 2377 ms 1597116 KB Output is correct
8 Correct 2 ms 16988 KB Output is correct
9 Correct 2 ms 17080 KB Output is correct
10 Correct 2427 ms 1594044 KB Output is correct
11 Correct 1259 ms 1526648 KB Output is correct
12 Correct 1552 ms 1571772 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1304 ms 791376 KB Output is correct
2 Correct 1352 ms 791380 KB Output is correct
3 Correct 1261 ms 788052 KB Output is correct
4 Incorrect 971 ms 779144 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1304 ms 791376 KB Output is correct
2 Correct 1352 ms 791380 KB Output is correct
3 Correct 1261 ms 788052 KB Output is correct
4 Incorrect 971 ms 779144 KB Output isn't correct
5 Halted 0 ms 0 KB -