oj.uz

Submission #35253

# Submission time Handle Problem Language Result Execution time Memory
35253 2017-11-19T09:34:16 Z bql20000 도로 건설 사업 (JOI13_construction) C++14
100 / 100
 1018 ms 40380 KB 
#include <bits/stdc++.h>

#define ff(i,a,b)       for(int i=(a), _b=(b); i<=_b; ++i)
#define gg(i,a,b)       for(int i=(a), _b=(b); i>=_b; --i)
#define REP(i,b)        for(int i=(0), _b=(b); i< _b; ++i)
#define endl            '\n'
#define long            long long
#define ALL(x)          (x).begin(), (x).end()
#define Love(a)         {cerr << #a << " = " << a << endl;}
#define _               << "," <<
#define BIT(i, x)       (((x)>>(i))&1)
#define X               first
#define Y               second
#define gc getchar
#define pc putchar

#define NAME            "Construction"

using namespace std;
const int N = 2e5 +  8, maxQ = 5e5 + 7;
typedef pair<int, int> ii;

inline void read(int &x){
    register int c = gc();
    x = 0;
    int neg = 0;
    for (;((c<48 || c>57) && c != '-') ;c = gc());
    if(c=='-') {neg=1;c=gc();}
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
}
inline void writeln(long x){

         char buffor[21];
         register int i=0;
         int neg=0; if (x<0) {neg=1; x= -x;}
         do{
               buffor[i++]=(x%10)+'0';
               x/=10;
            } while(x);
           i--;
           if (neg) pc('-');
           while(i>=0) pc(buffor[i--]);
           pc('\n');
       }

struct HCN {
    int x, y, u, v;
    HCN () {}
    HCN (int x, int y, int u, int v) : x(x), y(y), u(u), v(v) {}
}rect[N];

struct city {
    int x, y, id;
    city () {}
    bool operator < (const city &b) {
        return x < b.x || x == b.x && y < b.y;
    }
}a[N];

struct Doan {
    int x, l, r;
    bool open;
    Doan () {}
    Doan (int x, int l, int r, bool open) : x(x), l(l), r(r), open(open) {}
    bool operator < (const Doan &b) {return x < b.x;}
    void print() {
        cerr << x << ' ' << l << ' ' << r << ' ' << open << endl;
    }
}Line[2*N];

struct edge {
    int x, y, w;
    edge () {}
    edge (int x, int y, int w) : x(x), y(y), w(w) {}
    bool operator < (const edge &b) {return w < b.w;};
}e[2*N];


int n, m, Q, rankX, rankY, E, lab[N], TPLT;
long pre[N];

void Enter() {
    read(n);  read(m);  read(Q);

    ff(i, 1, n) {
        read(a[i].x); read(a[i].y);
        a[i].id = i;
    }
    ff(i, 1, m) {
        read(rect[i].x);
        read(rect[i].y);
        read(rect[i].u);
        read(rect[i].v);
    }
}

void CreateLine() {
    ff(i, 1, m) {
        Line[i] = Doan(rect[i].x, rect[i].y, rect[i].v, 1);
        Line[i+m] = Doan(rect[i].u+1, rect[i].y, rect[i].v, 0);     //rect[u]+1  => tri tue vai~
    }
    sort(Line+1, Line+1+2*m);
//    ff(i, 1, 2*m) {
//        Love(i); Line[i].print();
//    }
}

multiset<int> st;

void BuildEdge() {
    CreateLine();
    sort(a+1, a+1+n);       //sort cac diem theo x tang dan, x = nhau thi y tang dan
    //ff(i, 1, n) Love(i _ a[i].x _ a[i].y)

    st.clear();
    int k = 1;
    ff(i, 2, n)
        if (a[i].x == a[i-1].x) {
            for(; k <= 2*m && Line[k].x <= a[i].x; ++k) {
                if (Line[k].open) {
                    st.insert(Line[k].l);
                    st.insert(Line[k].r);
                }
                else {
                    st.erase(st.find(Line[k].l));
                    st.erase(st.find(Line[k].r));
                }
            }

            multiset<int> :: iterator it = st.lower_bound(a[i-1].y);
            if (it == st.end() || (*it) > a[i].y) {
                e[++E] = edge(a[i].id, a[i-1].id, a[i].y - a[i-1].y);
            }
        }
}

void Reverse() {
    ff(i, 1, n) {
        swap(a[i].x , a[i].y);
    }
    ff(i, 1, m) {
        swap(rect[i].x, rect[i].y);
        swap(rect[i].u, rect[i].v);
    }
}

int FindSet(int u) {
    return lab[u] < 0 ? u : lab[u] = FindSet(lab[u]);
}

void Union(int r, int s) {
    --TPLT;
    if (lab[r]  < lab[s]) swap(r, s);
    if (lab[r] == lab[s]) lab[s]--;
    lab[r] = s;
}

void Answer() {
    sort(e+1, e+1+E);

    fill_n(lab, n+1, -1);
    TPLT = n;
    vector <int> v;
    long res = 0;
    ff(i, 1, E) {
        int r = FindSet(e[i].x), s = FindSet(e[i].y);
        if (r != s) {
            Union(r, s);
            res += e[i].w;
            v.push_back(e[i].w);
        }
    }

    int top = v.size();
    REP(i, top) pre[i] = (i == 0 ? v[i] : pre[i-1] + v[i]);


    ff(i, 1, Q) {
        int w, cnt;
        read(w); read(cnt);
        if (cnt < TPLT) writeln(-1);
        else {
            //if (v.back() <= w) cout << pre[top-1] + 1ll * w * TPLT << endl;
            int x = v.end() - upper_bound(ALL(v), w);
            int can = min(cnt - TPLT, x);
            long ans = (can == top ? 0 : pre[top-can-1]) + 1ll * (can + TPLT) * w;
            writeln(ans);
        }
    }
}

void Process() {
    BuildEdge();
    Reverse();
    BuildEdge();
    //ff(i, 1, E) Love(e[i].x _ e[i].y _ e[i].w)
    Answer();
}

int main() {
    //ios_base::sync_with_stdio(0); cin.tie(0);
   //freopen(NAME".inp", "r", stdin);
   // freopen(NAME".out", "w", stdout);
    Enter();
    Process();
    return 0;
}

Compilation message

construction.cpp: In member function 'bool city::operator<(const city&)':
construction.cpp:57:36: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
         return x < b.x || x == b.x && y < b.y;
                                    ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20908 KB Output is correct
2 Correct 103 ms 21628 KB Output is correct
3 Correct 116 ms 21628 KB Output is correct
4 Correct 99 ms 22396 KB Output is correct
5 Correct 99 ms 22396 KB Output is correct
6 Correct 106 ms 21628 KB Output is correct
7 Correct 79 ms 22396 KB Output is correct
8 Correct 86 ms 22404 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 676 ms 22360 KB Output is correct
2 Correct 783 ms 22360 KB Output is correct
3 Correct 736 ms 22360 KB Output is correct
4 Correct 793 ms 22360 KB Output is correct
5 Correct 506 ms 21084 KB Output is correct
6 Correct 136 ms 22396 KB Output is correct
7 Correct 756 ms 22360 KB Output is correct
8 Correct 433 ms 22396 KB Output is correct
9 Correct 399 ms 22396 KB Output is correct
10 Correct 539 ms 40380 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 21628 KB Output is correct
2 Correct 366 ms 22396 KB Output is correct
3 Correct 329 ms 21628 KB Output is correct
4 Correct 283 ms 22396 KB Output is correct
5 Correct 206 ms 21244 KB Output is correct
6 Correct 466 ms 22396 KB Output is correct
7 Correct 453 ms 21628 KB Output is correct
8 Correct 353 ms 21628 KB Output is correct
9 Correct 286 ms 22396 KB Output is correct
10 Correct 389 ms 22404 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1018 ms 22360 KB Output is correct
2 Correct 483 ms 21568 KB Output is correct
3 Correct 846 ms 22360 KB Output is correct
4 Correct 203 ms 20916 KB Output is correct
5 Correct 873 ms 22360 KB Output is correct
6 Correct 259 ms 20908 KB Output is correct
7 Correct 723 ms 21964 KB Output is correct
8 Correct 959 ms 22360 KB Output is correct
9 Correct 596 ms 22396 KB Output is correct
10 Correct 686 ms 40380 KB Output is correct
11 Correct 359 ms 23332 KB Output is correct