oj.uz

Submission #661496

# Submission time Handle Problem Language Result Execution time Memory
661496 2022-11-26T00:26:24 Z Lobo Roads (CEOI20_roads) C++17
60 / 100
 1000 ms 18852 KB 
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 1e6+10;

int n, x[maxn], y[maxn];
pair<int,int> val[maxn];

dbl findy(int i, int xcur) {
    if(x[i] == x[i+1]) return y[i];
    return ((dbl) y[i+1]-y[i])/((dbl) x[i+1]-x[i])*((dbl) xcur-x[i]) + y[i];
}

void solve() {
    cin >> n;

    vector<pair<pair<int,int>,pair<int,int>>> pts;
    for(int i = 1; i <= 2*n; i+=2) {
        cin >> x[i] >> y[i];
        cin >> x[i+1] >> y[i+1];
        if(mp(x[i],y[i]) > mp(x[i+1],y[i+1])) {
            swap(x[i],x[i+1]);
            swap(y[i],y[i+1]);
        }
        pts.pb(mp(mp(x[i],y[i]),mp(i,1)));
        pts.pb(mp(mp(x[i+1],y[i+1]),mp(i,-1)));
    }

    sort(all(pts));

    x[2*n+1] = -inf1;
    x[2*n+2] = inf1;
    y[2*n+1] = -inf1;
    y[2*n+2] = -inf1;
    val[2*n+1] = mp(-inf1,-inf1);
    vector<int> vec;
    vec.pb(2*n+1);
    for(auto X : pts) {
        if(X.sc.sc == 1) {
            int i = X.sc.fr;
            int xcur = X.fr.fr;

            int id = 0; // vec[id] is the last one under i
            for(int j = 0; j < vec.size(); j++) {
                if(findy(vec[j],xcur) <= y[i]) {
                    id = j;
                }
                else {
                    break;
                }
            }

            if(val[vec[id]].fr != -inf1) {
                cout << x[i] << " " << y[i] << " " << val[vec[id]].fr << " " << val[vec[id]].sc << endl;
            }

            val[vec[id]] = mp(x[i],y[i]);
            val[i] = mp(x[i],y[i]);
            vector<int> newvec;
            for(int j = 0; j <= id; j++) {
                newvec.pb(vec[j]);
            }
            newvec.pb(i);
            for(int j = id+1; j < vec.size(); j++) {
                newvec.pb(vec[j]);
            }
            swap(vec,newvec);
        }
        else {
            int i = X.sc.fr;
            int xcur = X.fr.fr;

            int id = 0;
            for(int j = 0; j < vec.size(); j++) {
                if(vec[j] == i) {
                    id = j;
                    break;
                }
            }
            assert(id != 0);
            val[vec[id-1]] = mp(x[i+1],y[i+1]);

            vector<int> newvec;
            for(int j = 0; j < id; j++) {
                newvec.pb(vec[j]);
            }
            for(int j = id+1; j < vec.size(); j++) {
                newvec.pb(vec[j]);
            }
            swap(vec,newvec);
            // for(auto j : vec) {
                // cout << j << ", " << val[j].fr << " " << val[j].sc << "| ";
            // }cout << endl;
        }
    }
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

Compilation message

roads.cpp: In function 'void solve()':
roads.cpp:54:30: 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]
   54 |             for(int j = 0; j < vec.size(); j++) {
      |                            ~~^~~~~~~~~~~~
roads.cpp:74:33: 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]
   74 |             for(int j = id+1; j < vec.size(); j++) {
      |                               ~~^~~~~~~~~~~~
roads.cpp:84:30: 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]
   84 |             for(int j = 0; j < vec.size(); j++) {
      |                            ~~^~~~~~~~~~~~
roads.cpp:97:33: 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]
   97 |             for(int j = id+1; j < vec.size(); j++) {
      |                               ~~^~~~~~~~~~~~
roads.cpp:81:17: warning: unused variable 'xcur' [-Wunused-variable]
   81 |             int xcur = X.fr.fr;
      |                 ^~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 121 ms 5816 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 10 ms 2000 KB Output is correct
5 Correct 21 ms 3540 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 10 ms 2000 KB Output is correct
5 Correct 19 ms 3532 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 11 ms 2316 KB Output is correct
10 Correct 260 ms 18764 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 9 ms 1948 KB Output is correct
5 Correct 19 ms 3536 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 10 ms 2252 KB Output is correct
10 Correct 55 ms 9660 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 10 ms 2000 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 12 ms 2272 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 564 KB Output is correct
13 Correct 11 ms 2256 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 7 ms 1112 KB Output is correct
23 Correct 7 ms 1068 KB Output is correct
24 Correct 16 ms 1684 KB Output is correct
25 Correct 0 ms 340 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 119 ms 5856 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 10 ms 2308 KB Output is correct
7 Correct 19 ms 4080 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 13 ms 2376 KB Output is correct
12 Correct 266 ms 18852 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 10 ms 2256 KB Output is correct
17 Correct 53 ms 9572 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 7 ms 1092 KB Output is correct
27 Correct 7 ms 1120 KB Output is correct
28 Correct 15 ms 1748 KB Output is correct
29 Execution timed out 1085 ms 10128 KB Time limit exceeded
30 Halted 0 ms 0 KB -