oj.uz

Submission #963785

# Submission time Handle Problem Language Result Execution time Memory
963785 2024-04-15T16:50:07 Z RaresFelix Team Contest (JOI22_team) C++17
0 / 100
 1 ms 604 KB 
#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")

#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
#define int ll
using ll = long long;
using ld = long double;  // or double, if TL is tight
using str = string; 
using ii = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;

struct om {
    int x, y, z;
};

struct AIB { /// maxim pe prefix
    int n;
    vi V;
    AIB(int N) : n(N + 1), V(N + 1, -1) {}

    void update(int p, int v) {
        ++p;
        while(p < n) {
            V[p] = max(V[p], v);
            p += p & -p;
        }
    }

    int query(int p) {
        int re = -1;
        ++p;
        while(p) {
            re = max(re, V[p]);
            p -= p & -p;
        }
        return re;
    }
};

struct Plan {
    int n;
    ll re = -1;
    map<int, int> MY, MZ; /// normalizari pt coordonate

    AIB MaxY, MaxZ; /// Maximele pt coordonate, dar normalizate dupa cealalta coord

    Plan(int N, map<int, int> MY0, map<int, int> MZ0) : n(N),
        MY(MY0), MZ(MZ0), MaxY(N), MaxZ(N) {}

    void insert(int y, int z) {
        /// il leg pe y cu ceva mai mic ca el
        ll v = MaxY.query(MZ[z] - 1); 
        if(v != -1) re = max(re, v + z);
        v = MaxZ.query(MY[y] - 1); 
        if(v != -1) re = max(re, v + y);

        MaxZ.update(MY[y], z);
        MaxY.update(MZ[z], y);
    }

    ll query() {
        return re;
    }
};


signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    vector<om> V;
    vi Y, Z;
    for(int i = 0; i < n; ++i) {
        int x, y, z;
        cin >> x >> y >> z;

        Y.push_back(y);
        Z.push_back(z);

        V.push_back({x, y, z});
    }
    auto norm_map = [&](vi &A) {
        sort(all(A));
        A.resize(unique(all(A)) - A.begin());
        int cnt = 0;
        map<int, int> M;
        for(int i = 0; i < A.size(); ++i)
            M[A[i]] = i;
        return M;
    };
    sort(all(V), [&](auto a, auto b) { return a.x < b.x; });
    Plan Sol(n, norm_map(Y), norm_map(Z));
    ll re = -1;
    for(int i = 0; i < n; ++i) {
        int dr = i;
        while(dr + 1 < n && V[dr + 1].x == V[i].x) ++dr;
        ll cre = Sol.query();
        if(cre != -1) {
            cre += V[dr].x;
            re = max(re, cre);
        }
        for(int j = i; j <= dr; ++j)
            Sol.insert(V[j].y, V[j].z);
        i = dr;
    }
    cout << re << "\n";
    return 0;
}

Compilation message

team.cpp: In lambda function:
team.cpp:95:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for(int i = 0; i < A.size(); ++i)
      |                        ~~^~~~~~~~~~
team.cpp:93:13: warning: unused variable 'cnt' [-Wunused-variable]
   93 |         int cnt = 0;
      |             ^~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Incorrect 0 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Incorrect 0 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Incorrect 0 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -