oj.uz

Submission #909590

# Submission time Handle Problem Language Result Execution time Memory
909590 2024-01-17T09:33:11 Z bachhoangxuan 도로 건설 사업 (JOI13_construction) C++17
40 / 100
 2100 ms 89004 KB 
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/

#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define mpp make_pair
#define fi first
#define se second
const int inf=1e18;
const int mod=998244353;
const int maxn=200005;
const int bl=650;
const int maxs=655;
const int maxm=200005;
const int maxq=500005;
const int maxl=25;
const int maxa=1000000;
const int root=3;
int power(int a,int n){
    int res=1;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;n>>=1;
    }
    return res;
}
const int iroot=power(3,mod-2);
const int base=131;

vector<piii> e;

struct Rec{
    int x,y,u,v;
}rec[maxn];
int X[maxn],Y[maxn];
int n,m,q;

void build(){
    map<int,vector<pii>> mp;
    for(int i=1;i<=n;i++) mp[X[i]].push_back({Y[i],i});
    for(int i=1;i<=m;i++){
        mp[rec[i].x].push_back({rec[i].y,0});
        mp[rec[i].u+1].push_back({rec[i].y,-1});
    }
    set<int> s;
    for(auto &it:mp){
        vector<pii> cc;
        for(auto [p,id]:it.se){
            if(id==0) s.insert(p);
            else if(id==-1) s.erase(p);
            else cc.push_back({p,id});
        }
        sort(cc.begin(),cc.end());
        for(int i=0;i<(int)cc.size()-1;i++){
            int x=cc[i].fi;
            auto it=s.lower_bound(x);
            if(it==s.end() || cc[i+1].fi<*it){
                e.push_back({cc[i+1].fi-cc[i].fi,{cc[i].se,cc[i+1].se}});
            }
        }
    }
}

int par[maxn];
int findpar(int u){
    if(u!=par[u]) return par[u]=findpar(par[u]);
    return u;
}
bool unions(int u,int v){
    u=findpar(u);v=findpar(v);
    if(u==v) return false;
    return par[v]=u,true;
}

vector<pii> qq[maxn];
int val[maxn],res[maxq];

struct line{
    int a,b,p;
    bool operator<(line l){return a>l.a;}
    bool operator<(int k){return p<k;}
};
struct cvht{
    vector<line> x;
    int div(int a,int b){
        return a/b-((a^b)<0 && a%b);
    }
    bool isect(line &l,line y){
        if(l.a==y.a) l.p=(l.b<y.b)?inf:-inf;
        else l.p=div(y.b-l.b,l.a-y.a);
        return l.p>=y.p;
    }
    void add(line l){
        if(!x.empty()) isect(x.back(),l);
        while((int)x.size()>=2 && x[(int)x.size()-2].p>=x.back().p){
            x.pop_back();
            isect(x.back(),l);
        }
        x.push_back(l);
    }
    int query(int v){
        if(x.empty()) return -1;
        auto l=*lower_bound(x.begin(),x.end(),v);
        return l.a*v+l.b;
    }
}cht;

void solve(){
    cin >> n >> m >> q;
    for(int i=1;i<=n;i++) cin >> X[i] >> Y[i],par[i]=i;
    for(int i=1;i<=m;i++) cin >> rec[i].x >> rec[i].y >> rec[i].u >> rec[i].v;
    build();
    for(int i=1;i<=n;i++) swap(X[i],Y[i]);
    for(int i=1;i<=m;i++) swap(rec[i].x,rec[i].y),swap(rec[i].u,rec[i].v);
    build();

    sort(e.begin(),e.end());
    vector<int> d;
    for(auto [w,x]:e) if(unions(x.fi,x.se)) d.push_back(w);
    memset(val,-1,sizeof(val));
    val[n]=0;
    int sum=0;
    for(int i=0;i<(int)d.size();i++){
        sum+=d[i];
        val[n-i-1]=sum;
    }

    for(int i=1;i<=q;i++){
        int h,b;cin >> b >> h;
        qq[h].push_back({b,i});
    }
    for(int i=1;i<=n;i++){
        if(val[i]!=-1) cht.add({-i,val[i],inf});
        for(auto [x,id]:qq[i]) res[id]=cht.query(-x);
    }
    for(int i=1;i<=q;i++) cout << res[i] << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 16728 KB Output is correct
2 Correct 275 ms 37040 KB Output is correct
3 Correct 264 ms 38068 KB Output is correct
4 Correct 145 ms 33460 KB Output is correct
5 Correct 387 ms 48432 KB Output is correct
6 Correct 274 ms 39868 KB Output is correct
7 Correct 77 ms 33484 KB Output is correct
8 Correct 304 ms 46312 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 16728 KB Output is correct
2 Correct 275 ms 37040 KB Output is correct
3 Correct 264 ms 38068 KB Output is correct
4 Correct 145 ms 33460 KB Output is correct
5 Correct 387 ms 48432 KB Output is correct
6 Correct 274 ms 39868 KB Output is correct
7 Correct 77 ms 33484 KB Output is correct
8 Correct 304 ms 46312 KB Output is correct
9 Correct 2015 ms 88996 KB Output is correct
10 Correct 1860 ms 88864 KB Output is correct
11 Correct 1959 ms 89004 KB Output is correct
12 Correct 2100 ms 88704 KB Output is correct
13 Incorrect 314 ms 40088 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 16728 KB Output is correct
2 Correct 275 ms 37040 KB Output is correct
3 Correct 264 ms 38068 KB Output is correct
4 Correct 145 ms 33460 KB Output is correct
5 Correct 387 ms 48432 KB Output is correct
6 Correct 274 ms 39868 KB Output is correct
7 Correct 77 ms 33484 KB Output is correct
8 Correct 304 ms 46312 KB Output is correct
9 Correct 443 ms 65528 KB Output is correct
10 Correct 482 ms 62656 KB Output is correct
11 Correct 469 ms 52024 KB Output is correct
12 Correct 367 ms 52880 KB Output is correct
13 Correct 606 ms 50152 KB Output is correct
14 Correct 563 ms 61532 KB Output is correct
15 Correct 411 ms 64424 KB Output is correct
16 Correct 390 ms 63684 KB Output is correct
17 Correct 303 ms 57648 KB Output is correct
18 Correct 503 ms 58412 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 16728 KB Output is correct
2 Correct 275 ms 37040 KB Output is correct
3 Correct 264 ms 38068 KB Output is correct
4 Correct 145 ms 33460 KB Output is correct
5 Correct 387 ms 48432 KB Output is correct
6 Correct 274 ms 39868 KB Output is correct
7 Correct 77 ms 33484 KB Output is correct
8 Correct 304 ms 46312 KB Output is correct
9 Correct 2015 ms 88996 KB Output is correct
10 Correct 1860 ms 88864 KB Output is correct
11 Correct 1959 ms 89004 KB Output is correct
12 Correct 2100 ms 88704 KB Output is correct
13 Incorrect 314 ms 40088 KB Output isn't correct
14 Halted 0 ms 0 KB -