Submission #414916

#	Time	Username	Problem	Language	Result	Execution time	Memory
414916		Pro_ktmr	도로 건설 사업 (JOI13_construction)	C++17	100 / 100	4296 ms	140560 KiB

construction

#include"bits/stdc++.h"
#include<unordered_set>
#include<unordered_map>
#include<random>
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
int dx[4]={ 1,0,-1,0 };
int dy[4]={ 0,1,0,-1 };

struct UnionFind{
private:
    vector<int> par;
    vector<int> siz;
public:
    void init(int N){
        par.resize(N);
        siz.resize(N);
        for(int i=0; i<N; i++) par[i] = i;
        for(int i=0; i<N; i++) siz[i] = 1;
    }
    void unite(int a, int b){
        int rootA = root(a);
        int rootB = root(b);
        if(rootA == rootB) return;
        if(siz[rootA] < siz[rootB]) swap(rootA, rootB);
        par[rootB] = rootA;
        siz[rootA] += siz[rootB];
    }
    int root(int a){
        if(par[a] == a) return a;
        return par[a] = root(par[a]);
    }
    bool same(int a, int b){
        return root(a) == root(b);
    }
    int size(int a){
        return siz[root(a)];
    }
};

struct RMaxQ{
private:
    int N;
    vector<long long> node, lazy;
    vector<bool> lazyFlg;
    long long DEFAULT;
public:
    void init(int n, long long def=-9223372036854775807LL){
        DEFAULT = def;
        node.clear();
        lazy.clear();
        lazyFlg.clear();
        N = 1;
        while(N < n) N = (N<<1);
        for(int i=0; i<2*N-1; i++){
            node.push_back(DEFAULT);
            lazy.push_back(0LL);
            lazyFlg.push_back(false);
        }
    }
    void eval(int k, int l, int r){
        if(lazyFlg[k]){
            node[k] = lazy[k];
            if(r-l > 1){
                lazy[(k<<1)+1] = lazy[k];
                lazyFlg[(k<<1)+1] = true;
                lazy[(k<<1)+2] = lazy[k];
                lazyFlg[(k<<1)+2] = true;
            }
            lazy[k] = 0LL;
            lazyFlg[k] = false;
        }
        else{
            node[k] += lazy[k];
            if(r-l > 1){
                lazy[(k<<1)+1] += lazy[k];
                lazy[(k<<1)+2] += lazy[k];
            }
            lazy[k] = 0LL;
        }
    }
    void update(int a, long long x){
        update(a, a+1, x);
    }
    void update(int a, int b, long long x, int k=0, int l=0, int r=-1){
        if(a >= b) return;
        if(r == -1) r = N;
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b){
            lazy[k] = x;
            lazyFlg[k] = true;
            eval(k, l, r);
        }
        else{
            update(a, b, x, (k<<1)+1, l, (l+r)>>1);
            update(a, b, x, (k<<1)+2, (l+r)>>1, r);
            node[k] = std::max(node[(k<<1)+1], node[(k<<1)+2]);
        }
    }
    void add(int a, long long x){
        add(a, a+1, x);
    }
    void add(int a, int b, long long x, int k=0, int l=0, int r=-1){
        if(a >= b) return;
        if(r == -1) r = N;
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b){
            lazy[k] += x;
            eval(k, l, r);
        }
        else{
            add(a, b, x, (k<<1)+1, l, (l+r)>>1);
            add(a, b, x, (k<<1)+2, (l+r)>>1, r);
            node[k] = std::max(node[(k<<1)+1], node[(k<<1)+2]);
        }
    }
    long long max(int a, int b, int k=0, int l=0, int r=-1){
        if(a >= b) return -9223372036854775807LL;
        if(r == -1) r = N;
        if(b <= l || r <= a) return -9223372036854775807LL;
        eval(k, l, r);
        if(a <= l && r <= b) return node[k];
        return std::max(max(a, b, (k<<1)+1, l, (l+r)>>1), max(a, b, (k<<1)+2, (l+r)>>1, r));
    }
};

int N, M, C;
int X[200000], Y[200000];
vector<int> zX, zY;
int L[200000], U[200000], R[200000], D[200000]; // [)

vector<pair<int,int>> tmp[600000], tmpA[600000], tmpB[600000];
RMaxQ rmq;
vector<pair<ll,pair<int,int>>> edge;

UnionFind uf;
ll cost[200001];

const ll INF = 2'000'000'000'000'000'000LL;

signed main(){
    cin >> N >> M >> C;
    rep(i, N){
        cin >> X[i] >> Y[i];
        zX.pb(X[i]);
        zY.pb(Y[i]);
    }
    rep(i, M){
        cin >> L[i] >> U[i] >> R[i] >> D[i];
        R[i]++;
        D[i]++;
        zX.pb(L[i]); zX.pb(R[i]);
        zY.pb(U[i]); zY.pb(D[i]);
    }
    zX.pb(1e9+7);
    sort(all(zX));
    zX.erase(unique(all(zX)), zX.end());
    zY.pb(1e9+7);
    sort(all(zY));
    zY.erase(unique(all(zY)), zY.end());
    
    // |
    rep(i, N) tmp[lower_bound(all(zX), X[i])-zX.begin()]
        .pb({ lower_bound(all(zY), Y[i])-zY.begin(),i });
    rep(i, M){
        tmpA[lower_bound(all(zX), L[i])-zX.begin()]
            .pb({ lower_bound(all(zY), U[i])-zY.begin(), lower_bound(all(zY), D[i])-zY.begin() });
        tmpB[lower_bound(all(zX), R[i])-zX.begin()]
            .pb({ lower_bound(all(zY), U[i])-zY.begin(), lower_bound(all(zY), D[i])-zY.begin() });
    }
    rmq.init(zY.size(), 0);
    rep(i, zX.size()){
        rep(j, tmpA[i].size()) rmq.add(tmpA[i][j].first, tmpA[i][j].second, 1);
        rep(j, tmpB[i].size()) rmq.add(tmpB[i][j].first, tmpB[i][j].second, -1);
        sort(all(tmp[i]));
        rep(j, tmp[i].size()-1){
            if(rmq.max(tmp[i][j].first, tmp[i][j+1].first) == 0) 
                edge.pb({ zY[tmp[i][j+1].first]-zY[tmp[i][j].first], {tmp[i][j].second, tmp[i][j+1].second} });
        }
        tmp[i].clear();
        tmpA[i].clear();
        tmpB[i].clear();
    }
    // -
    rep(i, N) tmp[lower_bound(all(zY), Y[i])-zY.begin()]
        .pb({ lower_bound(all(zX), X[i])-zX.begin(),i });
    rep(i, M){
        tmpA[lower_bound(all(zY), U[i])-zY.begin()]
            .pb({ lower_bound(all(zX), L[i])-zX.begin(), lower_bound(all(zX), R[i])-zX.begin() });
        tmpB[lower_bound(all(zY), D[i])-zY.begin()]
            .pb({ lower_bound(all(zX), L[i])-zX.begin(), lower_bound(all(zX), R[i])-zX.begin() });
    }
    rmq.init(zX.size(), 0);
    rep(i, zY.size()){
        rep(j, tmpA[i].size()) rmq.add(tmpA[i][j].first, tmpA[i][j].second, 1);
        rep(j, tmpB[i].size()) rmq.add(tmpB[i][j].first, tmpB[i][j].second, -1);
        sort(all(tmp[i]));
        rep(j, tmp[i].size()-1){
            if(rmq.max(tmp[i][j].first, tmp[i][j+1].first) == 0)
                edge.pb({ zX[tmp[i][j+1].first]-zX[tmp[i][j].first], {tmp[i][j].second, tmp[i][j+1].second} });
        }
        tmp[i].clear();
        tmpA[i].clear();
        tmpB[i].clear();
    }

    sort(all(edge));
    uf.init(N);
    rep(i, N) cost[i+1] = INF;
    int cnt = N;
    cost[N] = 0;
    rep(i, edge.size()){
        //cout << "* " << edge[i].second.first << " " << edge[i].second.second << " " << edge[i].first << endl;
        if(uf.same(edge[i].second.first, edge[i].second.second)) continue;
        cnt--;
        cost[cnt] = cost[cnt+1] + edge[i].first;
        uf.unite(edge[i].second.first, edge[i].second.second);
    }

    //rep(i, N) cout << cost[i+1] << " ";
    //cout << endl;

    rep(q, C){
        ll B;
        int H;
        cin >> B >> H;
        if(cost[H] == INF){
            cout << -1 << endl;
            continue;
        }
        ll l = cnt, r = H+1; // [l, r)
        while(r-l > 1){
            ll m = (l+r)/2;
            if(cost[m-1]-cost[m] < B) r = m;
            else l = m;
        }
        //cout << ng << endl;
        cout << l*B+cost[l] << endl;
    }
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:11:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   11 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
construction.cpp:150:5: note: in expansion of macro 'rep'
  150 |     rep(i, N){
      |     ^~~
construction.cpp:11:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   11 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
construction.cpp:155:5: note: in expansion of macro 'rep'
  155 |     rep(i, M){
      |     ^~~
construction.cpp:11:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   11 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
construction.cpp:170:5: note: in expansion of macro 'rep'
  170 |     rep(i, N) tmp[lower_bound(all(zX), X[i])-zX.begin()]
      |     ^~~
construction.cpp:11:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   11 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
construction.cpp:172:5: note: in expansion of macro 'rep'
  172 |     rep(i, M){
      |     ^~~
construction.cpp:11:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   11 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
construction.cpp:179:5: note: in expansion of macro 'rep'
  179 |     rep(i, zX.size()){
      |     ^~~
construction.cpp:11:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   11 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
construction.cpp:180:9: note: in expansion of macro 'rep'
  180 |         rep(j, tmpA[i].size()) rmq.add(tmpA[i][j].first, tmpA[i][j].second, 1);
      |         ^~~
construction.cpp:11:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   11 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
construction.cpp:181:9: note: in expansion of macro 'rep'
  181 |         rep(j, tmpB[i].size()) rmq.add(tmpB[i][j].first, tmpB[i][j].second, -1);
      |         ^~~
construction.cpp:11:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   11 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
construction.cpp:183:9: note: in expansion of macro 'rep'
  183 |         rep(j, tmp[i].size()-1){
      |         ^~~
construction.cpp:11:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   11 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
construction.cpp:192:5: note: in expansion of macro 'rep'
  192 |     rep(i, N) tmp[lower_bound(all(zY), Y[i])-zY.begin()]
      |     ^~~
construction.cpp:11:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   11 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
construction.cpp:194:5: note: in expansion of macro 'rep'
  194 |     rep(i, M){
      |     ^~~
construction.cpp:11:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   11 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
construction.cpp:201:5: note: in expansion of macro 'rep'
  201 |     rep(i, zY.size()){
      |     ^~~
construction.cpp:11:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   11 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
construction.cpp:202:9: note: in expansion of macro 'rep'
  202 |         rep(j, tmpA[i].size()) rmq.add(tmpA[i][j].first, tmpA[i][j].second, 1);
      |         ^~~
construction.cpp:11:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   11 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
construction.cpp:203:9: note: in expansion of macro 'rep'
  203 |         rep(j, tmpB[i].size()) rmq.add(tmpB[i][j].first, tmpB[i][j].second, -1);
      |         ^~~
construction.cpp:11:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   11 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
construction.cpp:205:9: note: in expansion of macro 'rep'
  205 |         rep(j, tmp[i].size()-1){
      |         ^~~
construction.cpp:11:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   11 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
construction.cpp:216:5: note: in expansion of macro 'rep'
  216 |     rep(i, N) cost[i+1] = INF;
      |     ^~~
construction.cpp:11:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   11 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
construction.cpp:219:5: note: in expansion of macro 'rep'
  219 |     rep(i, edge.size()){
      |     ^~~
construction.cpp:11:27: warning: unnecessary parentheses in declaration of 'q' [-Wparentheses]
   11 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
construction.cpp:230:5: note: in expansion of macro 'rep'
  230 |     rep(q, C){
      |     ^~~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30