oj.uz

Submission #632187

# Submission time Handle Problem Language Result Execution time Memory
632187 2022-08-19T15:21:49 Z minhcool 도로 건설 사업 (JOI13_construction) C++17
40 / 100
 5000 ms 171324 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define y1 y11
#define double long double
#define int long long
#define fi first
#define se second
#define pb push_back
//#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 6e5 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
int n, m, c;
int x[N], y[N];
 
int a[N], b[N], ccc[N], d[N];
 
map<int, vector<ii>> mp1, mp2;
 
vector<pair<int, ii>> edges;
 
int cc[N], mx[N];
 
int tol[N];
 
int sz[N], root[N];
 
int rt(int x){
    return (x == root[x] ? x : rt(root[x]));
}
 
bool merge(int x, int y){
    x = rt(x), y = rt(y);
    if(x == y) return 0;
    if(sz[x] < sz[y]) swap(x, y);
    sz[x] += sz[y];
    root[y] = x;
    return 1;
}

vector<int> vc1, vc2;
map<int, int> m1, m2;

int IT[N << 2], lazy[N << 2];

void laz(int id, int l, int r){
    int t = lazy[id];
    int mid = (l + r) >> 1;
    lazy[id << 1] += t;
    lazy[id << 1 | 1] += t;
    IT[id << 1] += t * (mid - l + 1);
    IT[id << 1 | 1] += t * (r - mid);
    lazy[id] = 0;
}

void upd(int id, int l, int r, int L, int R, int val){
    if(l > R || r < L) return;
    if(l >= L && r <= R){
        IT[id] += val * (r - l + 1);
        lazy[id] += val;
        return;
    }
    laz(id, l, r);
    int mid = (l + r) >> 1;
    upd(id << 1, l, mid, L, R, val);
    upd(id << 1 | 1, mid + 1, r, L, R, val);
    IT[id] = IT[id << 1] + IT[id << 1 | 1];
}

int get(int id, int l, int r, int L, int R){
    if(l > R || r < L) return 0;
    if(l >= L && r <= R) return IT[id];
    laz(id, l, r);
    int mid = (l + r) >> 1;
    return get(id << 1, l, mid, L, R) + get(id << 1 | 1, mid + 1, r, L, R);
}
 
void process(){
    cin >> n >> m >> c;
    for(int i = 1; i <= n; i++){
        cin >> x[i] >> y[i];
        mp1[x[i]].pb({y[i], i});
        mp2[y[i]].pb({x[i], i});
        vc1.pb(x[i]), vc2.pb(y[i]);
    }
    vector<iii> events;
    for(int i = 1; i <= m; i++){
        cin >> a[i] >> b[i] >> ccc[i] >> d[i];
        events.pb({{a[i], i}, 1});
        events.pb({{ccc[i] + 1, i}, -1});
        vc1.pb(a[i]);
        vc2.pb(b[i]);
        vc1.pb(ccc[i]);
        vc2.pb(d[i]);
    }
    sort(vc1.begin(), vc1.end());
    sort(vc2.begin(), vc2.end());
    for(int i = 0; i < vc1.size(); i++) m1[vc1[i]] = i + 1;
    for(int i = 0; i < vc2.size(); i++) m2[vc2[i]] = i + 1;
    sort(events.begin(), events.end());
    int itr = 0;
    //return;
    for(map<int, vector<ii>>::iterator it = mp1.begin(); it != mp1.end(); it++){
        while(itr < events.size() && events[itr].fi.fi <= (*it).fi){
            int ind = events[itr].fi.se;
            upd(1, 1, vc2.size(), m2[b[ind]], m2[d[ind]], events[itr].se);
            itr++;
        }
        vector<ii> temp = (*it).se;
        sort(temp.begin(), temp.end());
        for(int i = 1; i < temp.size(); i++){
            //cout << (*it).fi << " " << temp[i - 1].fi << " " << temp[i].fi << "\n";
            if(get(1, 1, vc2.size(), m2[temp[i - 1].fi], m2[temp[i].fi]) > 0) continue;
            //cout << (*it).fi << " " << temp[i - 1].fi << " " << temp[i].fi << "\n";
            //cout << "1 " << temp[i].se << " " << temp[i - 1].se << "\n";
            edges.pb({temp[i].fi - temp[i - 1].fi, {temp[i].se, temp[i - 1].se}});
        }
    }
    for(int i = 1; i <= (vc2.size() << 2); i++) IT[i] = lazy[i] = 0;
    events.clear();
    for(int i = 1; i <= m; i++){
        events.pb({{b[i], i}, 1});
        events.pb({{d[i] + 1, i}, -1});
    }
    sort(events.begin(), events.end());
    itr = 0;
    for(map<int, vector<ii>>::iterator it = mp2.begin(); it != mp2.end(); it++){
        while(itr < events.size() && events[itr].fi.fi <= (*it).fi){
            int ind = events[itr].fi.se;
            upd(1, 1, vc1.size(), m1[a[ind]], m1[ccc[ind]], events[itr].se);
            itr++;
        }
        vector<ii> temp = (*it).se;
        sort(temp.begin(), temp.end());
        for(int i = 1; i < temp.size(); i++){
            //cout << (*it).fi << " " << temp[i - 1].fi << " " << temp[i].fi << "\n";
            if(get(1, 1, vc1.size(), m1[temp[i - 1].fi], m1[temp[i].fi]) > 0) continue;
            //cout << (*it).fi << " " << temp[i - 1].fi << " " << temp[i].fi << "\n";
            //cout << "2 " << (*it).fi << " " << temp[i].se << " " << temp[i - 1].se << "\n";
            edges.pb({temp[i].fi - temp[i - 1].fi, {temp[i].se, temp[i - 1].se}});
        }
    }
    //return;
    sort(edges.begin(), edges.end());
    int cnt = n;
    for(int i = 1; i <= n; i++){
        sz[i] = 1, root[i] = i;
    }
    for(auto it : edges){
        //cout << it.se.fi << " " << it.se.se << "\n";
        //continue;
        if(merge(it.se.fi, it.se.se)){
            cnt--;
            assert(cnt >= 0);
            tol[cnt] = tol[cnt + 1] + it.fi;
            //cout << cnt << " " << tol[cnt] << "\n";
        }
    }
    //return;
    for(int i = 0; i < cnt; i++) tol[i] = oo;
    //for(int i = 0; i <= n; i++) cout << tol[i] << "\n";
    for(int i = 1; i <= c; i++){
        cin >> cc[i] >> mx[i];
        int answer = oo;
        for(int j = 0; j <= mx[i]; j++) answer = min(answer, cc[i] * j + tol[j]);
        cout << (answer == oo ? -1 : answer) << "\n";
    }
}
 
signed main(){
	ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) process();
}

Compilation message

construction.cpp: In function 'void process()':
construction.cpp:107:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for(int i = 0; i < vc1.size(); i++) m1[vc1[i]] = i + 1;
      |                    ~~^~~~~~~~~~~~
construction.cpp:108:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     for(int i = 0; i < vc2.size(); i++) m2[vc2[i]] = i + 1;
      |                    ~~^~~~~~~~~~~~
construction.cpp:113:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |         while(itr < events.size() && events[itr].fi.fi <= (*it).fi){
      |               ~~~~^~~~~~~~~~~~~~~
construction.cpp:120:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         for(int i = 1; i < temp.size(); i++){
      |                        ~~^~~~~~~~~~~~~
construction.cpp:128:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for(int i = 1; i <= (vc2.size() << 2); i++) IT[i] = lazy[i] = 0;
      |                    ~~^~~~~~~~~~~~~~~~~~~~
construction.cpp:137:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |         while(itr < events.size() && events[itr].fi.fi <= (*it).fi){
      |               ~~~~^~~~~~~~~~~~~~~
construction.cpp:144:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |         for(int i = 1; i < temp.size(); i++){
      |                        ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 4624 KB Output is correct
2 Correct 795 ms 67820 KB Output is correct
3 Correct 740 ms 66556 KB Output is correct
4 Correct 519 ms 45428 KB Output is correct
5 Correct 786 ms 68760 KB Output is correct
6 Correct 701 ms 66600 KB Output is correct
7 Correct 269 ms 42168 KB Output is correct
8 Correct 441 ms 69248 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 4624 KB Output is correct
2 Correct 795 ms 67820 KB Output is correct
3 Correct 740 ms 66556 KB Output is correct
4 Correct 519 ms 45428 KB Output is correct
5 Correct 786 ms 68760 KB Output is correct
6 Correct 701 ms 66600 KB Output is correct
7 Correct 269 ms 42168 KB Output is correct
8 Correct 441 ms 69248 KB Output is correct
9 Correct 3310 ms 159544 KB Output is correct
10 Correct 3454 ms 171228 KB Output is correct
11 Correct 3930 ms 171324 KB Output is correct
12 Correct 3608 ms 171280 KB Output is correct
13 Correct 1417 ms 89480 KB Output is correct
14 Correct 765 ms 72800 KB Output is correct
15 Correct 3715 ms 171152 KB Output is correct
16 Correct 852 ms 100860 KB Output is correct
17 Correct 784 ms 100864 KB Output is correct
18 Correct 1323 ms 153692 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 4624 KB Output is correct
2 Correct 795 ms 67820 KB Output is correct
3 Correct 740 ms 66556 KB Output is correct
4 Correct 519 ms 45428 KB Output is correct
5 Correct 786 ms 68760 KB Output is correct
6 Correct 701 ms 66600 KB Output is correct
7 Correct 269 ms 42168 KB Output is correct
8 Correct 441 ms 69248 KB Output is correct
9 Execution timed out 5070 ms 67136 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 4624 KB Output is correct
2 Correct 795 ms 67820 KB Output is correct
3 Correct 740 ms 66556 KB Output is correct
4 Correct 519 ms 45428 KB Output is correct
5 Correct 786 ms 68760 KB Output is correct
6 Correct 701 ms 66600 KB Output is correct
7 Correct 269 ms 42168 KB Output is correct
8 Correct 441 ms 69248 KB Output is correct
9 Correct 3310 ms 159544 KB Output is correct
10 Correct 3454 ms 171228 KB Output is correct
11 Correct 3930 ms 171324 KB Output is correct
12 Correct 3608 ms 171280 KB Output is correct
13 Correct 1417 ms 89480 KB Output is correct
14 Correct 765 ms 72800 KB Output is correct
15 Correct 3715 ms 171152 KB Output is correct
16 Correct 852 ms 100860 KB Output is correct
17 Correct 784 ms 100864 KB Output is correct
18 Correct 1323 ms 153692 KB Output is correct
19 Execution timed out 5070 ms 67136 KB Time limit exceeded
20 Halted 0 ms 0 KB -