Submission #553755

#	Time	Username	Problem	Language	Result	Execution time	Memory
553755		LucaDantas	Team Contest (JOI22_team)	C++17	36 / 100	96 ms	8660 KiB

team

#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
    pair<int,int> ans;
    void calc(int x, int y) {
        int maior = seg.query(0, x-1);
        if(maior > y)
            // ans.push_back({x, maior});
            ans = max(ans, {x, maior});
        int pos = seg.find(y);
        if(pos > x)
            ans = max(ans, {pos, y});
            // 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)
        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 (stderr)

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

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 0 / 27