oj.uz

Submission #591883

# Submission time Handle Problem Language Result Execution time Memory
591883 2022-07-08T05:56:29 Z 반딧불(#8422) Team Contest (JOI22_team) C++17
36 / 100
 798 ms 71152 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct segTree{
    int tree[600002];

    void init(int i, int l, int r){
        tree[i] = -1e9;
        if(l==r) return;
        int m = (l+r)>>1;
        init(i*2, l, m), init(i*2+1, m+1, r);
    }

    void update(int i, int l, int r, int x, int v){
        if(l==r){
            tree[i] = max(tree[i], v);
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) update(i*2, l, m, x, v);
        else update(i*2+1, m+1, r, x, v);
        tree[i] = max(tree[i*2], tree[i*2+1]);
    }

    int query(int i, int l, int r, int s, int e){
        if(r<s || e<l) return -1e9;
        if(s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return max(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
    }
} tree;

struct dat{
    int y, z, i;
    dat(){}
    dat(int y, int z, int i): y(y), z(z), i(i){}

    bool operator<(const dat &r)const{
        if(y!=r.y) return y<r.y;
        return z<r.z;
    }
};

int n;
int x[150002], y[150002], z[150002];
int yIdx[150002];
int ans = -1;

int mat[4002][4002];
vector<dat> xVec[4002], yVec[4002];

void clean(vector<dat> &vec){
    vector<dat> tvec;
    tvec.swap(vec);
    sort(tvec.begin(), tvec.end());
    for(dat p: tvec){
        if(!vec.empty() && vec.back().z <= p.z) continue;
        vec.push_back(p);
    }
}

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d %d %d", &x[i], &y[i], &z[i]);
        mat[x[i]][y[i]] = max(mat[x[i]][y[i]], z[i]);
        xVec[x[i]].push_back(dat(y[i], z[i], i));
        yVec[y[i]].push_back(dat(x[i], z[i], i));
    }

    for(int i=1; i<=4000; i++){
        for(int j=1; j<=4000; j++){
            mat[i][j] = max({mat[i][j], mat[i-1][j], mat[i][j-1]});
        }
    }
    for(int i=1; i<=4000; i++){
        clean(xVec[i]);
        clean(yVec[i]);
    }

    for(int I=1; I<=4000; I++){
        for(int J=1; J<=4000; J++){
            auto it1 = lower_bound(xVec[I].begin(), xVec[I].end(), dat(J, -1, -1));
            auto it2 = lower_bound(yVec[J].begin(), yVec[J].end(), dat(I, -1, -1));
            if(it1 == xVec[I].begin() || it2 == yVec[J].begin()) continue;
            int i = prev(it1)->i, j = prev(it2)->i;
            if(i==j) continue;
            if(x[i] <= x[j] || y[i] >= y[j]) continue;
            int tmp = mat[x[i]-1][y[j]-1];
            if(tmp > z[i] && tmp > z[j]) ans = max(ans, x[i]+y[j]+tmp);
        }
    }

    printf("%d", ans);
}

Compilation message

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

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 63052 KB Output is correct
2 Correct 157 ms 63144 KB Output is correct
3 Correct 172 ms 63152 KB Output is correct
4 Correct 167 ms 63152 KB Output is correct
5 Correct 175 ms 63152 KB Output is correct
6 Correct 153 ms 63092 KB Output is correct
7 Correct 163 ms 63152 KB Output is correct
8 Correct 167 ms 63152 KB Output is correct
9 Correct 162 ms 63152 KB Output is correct
10 Correct 166 ms 63264 KB Output is correct
11 Correct 157 ms 63152 KB Output is correct
12 Correct 166 ms 63056 KB Output is correct
13 Correct 162 ms 63052 KB Output is correct
14 Runtime error 2 ms 788 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 169 ms 63052 KB Output is correct
2 Correct 157 ms 63144 KB Output is correct
3 Correct 172 ms 63152 KB Output is correct
4 Correct 167 ms 63152 KB Output is correct
5 Correct 175 ms 63152 KB Output is correct
6 Correct 153 ms 63092 KB Output is correct
7 Correct 163 ms 63152 KB Output is correct
8 Correct 167 ms 63152 KB Output is correct
9 Correct 162 ms 63152 KB Output is correct
10 Correct 166 ms 63264 KB Output is correct
11 Correct 157 ms 63152 KB Output is correct
12 Correct 166 ms 63056 KB Output is correct
13 Correct 162 ms 63052 KB Output is correct
14 Runtime error 2 ms 788 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 63152 KB Output is correct
2 Correct 158 ms 63148 KB Output is correct
3 Correct 170 ms 63160 KB Output is correct
4 Correct 165 ms 63088 KB Output is correct
5 Correct 167 ms 63148 KB Output is correct
6 Correct 174 ms 63192 KB Output is correct
7 Correct 167 ms 63148 KB Output is correct
8 Correct 157 ms 63048 KB Output is correct
9 Correct 164 ms 63148 KB Output is correct
10 Correct 159 ms 63108 KB Output is correct
11 Correct 207 ms 68560 KB Output is correct
12 Correct 198 ms 67180 KB Output is correct
13 Correct 197 ms 67676 KB Output is correct
14 Correct 205 ms 68992 KB Output is correct
15 Correct 199 ms 69176 KB Output is correct
16 Correct 219 ms 68640 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 63152 KB Output is correct
2 Correct 158 ms 63148 KB Output is correct
3 Correct 170 ms 63160 KB Output is correct
4 Correct 165 ms 63088 KB Output is correct
5 Correct 167 ms 63148 KB Output is correct
6 Correct 174 ms 63192 KB Output is correct
7 Correct 167 ms 63148 KB Output is correct
8 Correct 157 ms 63048 KB Output is correct
9 Correct 164 ms 63148 KB Output is correct
10 Correct 159 ms 63108 KB Output is correct
11 Correct 207 ms 68560 KB Output is correct
12 Correct 198 ms 67180 KB Output is correct
13 Correct 197 ms 67676 KB Output is correct
14 Correct 205 ms 68992 KB Output is correct
15 Correct 199 ms 69176 KB Output is correct
16 Correct 219 ms 68640 KB Output is correct
17 Correct 153 ms 63068 KB Output is correct
18 Correct 153 ms 63060 KB Output is correct
19 Correct 199 ms 63152 KB Output is correct
20 Correct 157 ms 63084 KB Output is correct
21 Correct 163 ms 63268 KB Output is correct
22 Correct 233 ms 69036 KB Output is correct
23 Correct 209 ms 68992 KB Output is correct
24 Correct 216 ms 67884 KB Output is correct
25 Correct 224 ms 69376 KB Output is correct
26 Correct 226 ms 68744 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 63152 KB Output is correct
2 Correct 158 ms 63148 KB Output is correct
3 Correct 170 ms 63160 KB Output is correct
4 Correct 165 ms 63088 KB Output is correct
5 Correct 167 ms 63148 KB Output is correct
6 Correct 174 ms 63192 KB Output is correct
7 Correct 167 ms 63148 KB Output is correct
8 Correct 157 ms 63048 KB Output is correct
9 Correct 164 ms 63148 KB Output is correct
10 Correct 159 ms 63108 KB Output is correct
11 Correct 207 ms 68560 KB Output is correct
12 Correct 198 ms 67180 KB Output is correct
13 Correct 197 ms 67676 KB Output is correct
14 Correct 205 ms 68992 KB Output is correct
15 Correct 199 ms 69176 KB Output is correct
16 Correct 219 ms 68640 KB Output is correct
17 Correct 153 ms 63068 KB Output is correct
18 Correct 153 ms 63060 KB Output is correct
19 Correct 199 ms 63152 KB Output is correct
20 Correct 157 ms 63084 KB Output is correct
21 Correct 163 ms 63268 KB Output is correct
22 Correct 233 ms 69036 KB Output is correct
23 Correct 209 ms 68992 KB Output is correct
24 Correct 216 ms 67884 KB Output is correct
25 Correct 224 ms 69376 KB Output is correct
26 Correct 226 ms 68744 KB Output is correct
27 Correct 171 ms 63112 KB Output is correct
28 Correct 160 ms 63176 KB Output is correct
29 Correct 173 ms 63172 KB Output is correct
30 Correct 155 ms 63152 KB Output is correct
31 Correct 164 ms 63364 KB Output is correct
32 Correct 173 ms 63116 KB Output is correct
33 Correct 162 ms 63200 KB Output is correct
34 Correct 216 ms 69196 KB Output is correct
35 Correct 226 ms 70032 KB Output is correct
36 Correct 237 ms 70492 KB Output is correct
37 Correct 217 ms 69964 KB Output is correct
38 Correct 211 ms 68988 KB Output is correct
39 Correct 214 ms 67056 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 63152 KB Output is correct
2 Correct 158 ms 63148 KB Output is correct
3 Correct 170 ms 63160 KB Output is correct
4 Correct 165 ms 63088 KB Output is correct
5 Correct 167 ms 63148 KB Output is correct
6 Correct 174 ms 63192 KB Output is correct
7 Correct 167 ms 63148 KB Output is correct
8 Correct 157 ms 63048 KB Output is correct
9 Correct 164 ms 63148 KB Output is correct
10 Correct 159 ms 63108 KB Output is correct
11 Correct 207 ms 68560 KB Output is correct
12 Correct 198 ms 67180 KB Output is correct
13 Correct 197 ms 67676 KB Output is correct
14 Correct 205 ms 68992 KB Output is correct
15 Correct 199 ms 69176 KB Output is correct
16 Correct 219 ms 68640 KB Output is correct
17 Correct 153 ms 63068 KB Output is correct
18 Correct 153 ms 63060 KB Output is correct
19 Correct 199 ms 63152 KB Output is correct
20 Correct 157 ms 63084 KB Output is correct
21 Correct 163 ms 63268 KB Output is correct
22 Correct 233 ms 69036 KB Output is correct
23 Correct 209 ms 68992 KB Output is correct
24 Correct 216 ms 67884 KB Output is correct
25 Correct 224 ms 69376 KB Output is correct
26 Correct 226 ms 68744 KB Output is correct
27 Correct 171 ms 63112 KB Output is correct
28 Correct 160 ms 63176 KB Output is correct
29 Correct 173 ms 63172 KB Output is correct
30 Correct 155 ms 63152 KB Output is correct
31 Correct 164 ms 63364 KB Output is correct
32 Correct 173 ms 63116 KB Output is correct
33 Correct 162 ms 63200 KB Output is correct
34 Correct 216 ms 69196 KB Output is correct
35 Correct 226 ms 70032 KB Output is correct
36 Correct 237 ms 70492 KB Output is correct
37 Correct 217 ms 69964 KB Output is correct
38 Correct 211 ms 68988 KB Output is correct
39 Correct 214 ms 67056 KB Output is correct
40 Correct 223 ms 63312 KB Output is correct
41 Correct 200 ms 63504 KB Output is correct
42 Correct 182 ms 63344 KB Output is correct
43 Correct 167 ms 63364 KB Output is correct
44 Correct 798 ms 71152 KB Output is correct
45 Correct 506 ms 70360 KB Output is correct
46 Correct 558 ms 70764 KB Output is correct
47 Correct 497 ms 70452 KB Output is correct
48 Correct 251 ms 69004 KB Output is correct

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 63052 KB Output is correct
2 Correct 157 ms 63144 KB Output is correct
3 Correct 172 ms 63152 KB Output is correct
4 Correct 167 ms 63152 KB Output is correct
5 Correct 175 ms 63152 KB Output is correct
6 Correct 153 ms 63092 KB Output is correct
7 Correct 163 ms 63152 KB Output is correct
8 Correct 167 ms 63152 KB Output is correct
9 Correct 162 ms 63152 KB Output is correct
10 Correct 166 ms 63264 KB Output is correct
11 Correct 157 ms 63152 KB Output is correct
12 Correct 166 ms 63056 KB Output is correct
13 Correct 162 ms 63052 KB Output is correct
14 Runtime error 2 ms 788 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -