oj.uz

Submission #553753

# Submission time Handle Problem Language Result Execution time Memory
553753 2022-04-26T20:13:12 Z LucaDantas Team Contest (JOI22_team) C++17
0 / 100
 2000 ms 8660 KB 
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 1<<18; // tem q ser pot de 2 pra seg

struct Pt {
    int x, y, z;
    bool operator<(const Pt& o) { return z < o.z; }
} pt[maxn];

struct SegmentTree {
    int mx[maxn<<1], mn[maxn<<1];
    SegmentTree() { for(int i = 0; i < (maxn<<1); i++) mx[i] = -0x3f3f3f3f, mn[i] = 0x3f3f3f3f; }
    void upd(int x, int v) {
        // printf("upd %d %d\n", x, v);
        x += maxn;
        for(mx[x] = max(mx[x], v), mn[x] = min(mn[x], v); x > 1; x >>= 1)
            mx[x>>1] = max(mx[x], mx[x^1]), mn[x>>1] = min(mn[x], mn[x^1]);
    }
    int query(int l, int r) {
        // maximum in this segment
        // printf("query %d %d == ", l, r);
        r++;
        int ans = -0x3f3f3f3f;
        for(l += maxn, r += maxn; l < r; l >>= 1, r >>= 1) {
            if(l&1) ans = max(ans, mx[l++]);
            if(r&1) ans = max(ans, mx[--r]);
        }
        // printf("%d\n", ans);
        return ans;
    }
    int find(int v) {
        int x = 1;
        while(x < maxn)
            if(mn[x<<1|1] < v)
                x <<= 1, x |= 1;
            else
                x <<= 1;
        // printf("find - %d %d\n", v, x-maxn);
        return x - maxn;
    }
} seg;

struct ST {
    vector<pair<int,int>> ans; // still brute
    void calc(int x, int y) {
        int maior = seg.query(0, x-1);
        if(maior > y)
            ans.push_back({x, maior});
        int pos = seg.find(y);
        if(pos > x)
            ans.push_back({pos, y});
    }
    void insert(int x, int y) { seg.upd(x, y); }
    int get(int x, int y) {
        int aq = -0x3f3f3f3f;
        for(auto [x2, y2] : ans)
            if(x2 > x && y2 > y) aq = max(aq, x2+y2);
        return aq;
    }
} st;

int main() {
    int n; scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        int x, y, z; scanf("%d %d %d", &x, &y, &z);
        pt[i] = {x, y, z};
    }
    sort(pt, pt+n);
    int ans = -1;
    for(int i = 0, j = 0; i < n; i = j) {
        for(; j < n && pt[i].z == pt[j].z; j++)
            ans = max(ans, st.get(pt[j].x, pt[j].y) + pt[j].z);
        for(j = i; j < n && pt[i].z == pt[j].z; j++)
            st.insert(pt[j].x, pt[j].y);
        for(j = i; j < n && pt[i].z == pt[j].z; j++)
            st.calc(pt[j].x, pt[j].y);
        // puts("");
    }
    printf("%d\n", ans);
}

Compilation message

team.cpp: In function 'int main()':
team.cpp:64:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     int n; scanf("%d", &n);
      |            ~~~~~^~~~~~~~~~
team.cpp:66:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         int x, y, z; scanf("%d %d %d", &x, &y, &z);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4308 KB Output is correct
2 Correct 2 ms 4308 KB Output is correct
3 Correct 2 ms 4308 KB Output is correct
4 Correct 2 ms 4308 KB Output is correct
5 Correct 3 ms 4412 KB Output is correct
6 Correct 2 ms 4408 KB Output is correct
7 Correct 2 ms 4308 KB Output is correct
8 Correct 2 ms 4308 KB Output is correct
9 Correct 2 ms 4308 KB Output is correct
10 Correct 2 ms 4308 KB Output is correct
11 Correct 2 ms 4308 KB Output is correct
12 Correct 2 ms 4308 KB Output is correct
13 Correct 2 ms 4308 KB Output is correct
14 Runtime error 6 ms 8660 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4308 KB Output is correct
2 Correct 2 ms 4308 KB Output is correct
3 Correct 2 ms 4308 KB Output is correct
4 Correct 2 ms 4308 KB Output is correct
5 Correct 3 ms 4412 KB Output is correct
6 Correct 2 ms 4408 KB Output is correct
7 Correct 2 ms 4308 KB Output is correct
8 Correct 2 ms 4308 KB Output is correct
9 Correct 2 ms 4308 KB Output is correct
10 Correct 2 ms 4308 KB Output is correct
11 Correct 2 ms 4308 KB Output is correct
12 Correct 2 ms 4308 KB Output is correct
13 Correct 2 ms 4308 KB Output is correct
14 Runtime error 6 ms 8660 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4416 KB Output is correct
2 Correct 2 ms 4308 KB Output is correct
3 Correct 2 ms 4308 KB Output is correct
4 Correct 2 ms 4320 KB Output is correct
5 Correct 2 ms 4308 KB Output is correct
6 Correct 2 ms 4412 KB Output is correct
7 Correct 2 ms 4308 KB Output is correct
8 Correct 3 ms 4412 KB Output is correct
9 Correct 3 ms 4308 KB Output is correct
10 Correct 2 ms 4416 KB Output is correct
11 Execution timed out 2071 ms 7292 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4416 KB Output is correct
2 Correct 2 ms 4308 KB Output is correct
3 Correct 2 ms 4308 KB Output is correct
4 Correct 2 ms 4320 KB Output is correct
5 Correct 2 ms 4308 KB Output is correct
6 Correct 2 ms 4412 KB Output is correct
7 Correct 2 ms 4308 KB Output is correct
8 Correct 3 ms 4412 KB Output is correct
9 Correct 3 ms 4308 KB Output is correct
10 Correct 2 ms 4416 KB Output is correct
11 Execution timed out 2071 ms 7292 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4416 KB Output is correct
2 Correct 2 ms 4308 KB Output is correct
3 Correct 2 ms 4308 KB Output is correct
4 Correct 2 ms 4320 KB Output is correct
5 Correct 2 ms 4308 KB Output is correct
6 Correct 2 ms 4412 KB Output is correct
7 Correct 2 ms 4308 KB Output is correct
8 Correct 3 ms 4412 KB Output is correct
9 Correct 3 ms 4308 KB Output is correct
10 Correct 2 ms 4416 KB Output is correct
11 Execution timed out 2071 ms 7292 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4416 KB Output is correct
2 Correct 2 ms 4308 KB Output is correct
3 Correct 2 ms 4308 KB Output is correct
4 Correct 2 ms 4320 KB Output is correct
5 Correct 2 ms 4308 KB Output is correct
6 Correct 2 ms 4412 KB Output is correct
7 Correct 2 ms 4308 KB Output is correct
8 Correct 3 ms 4412 KB Output is correct
9 Correct 3 ms 4308 KB Output is correct
10 Correct 2 ms 4416 KB Output is correct
11 Execution timed out 2071 ms 7292 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4308 KB Output is correct
2 Correct 2 ms 4308 KB Output is correct
3 Correct 2 ms 4308 KB Output is correct
4 Correct 2 ms 4308 KB Output is correct
5 Correct 3 ms 4412 KB Output is correct
6 Correct 2 ms 4408 KB Output is correct
7 Correct 2 ms 4308 KB Output is correct
8 Correct 2 ms 4308 KB Output is correct
9 Correct 2 ms 4308 KB Output is correct
10 Correct 2 ms 4308 KB Output is correct
11 Correct 2 ms 4308 KB Output is correct
12 Correct 2 ms 4308 KB Output is correct
13 Correct 2 ms 4308 KB Output is correct
14 Runtime error 6 ms 8660 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -