oj.uz

Submission #69083

# Submission time Handle Problem Language Result Execution time Memory
69083 2018-08-20T01:16:12 Z Diuven None (KOI18_matrix) C++14
100 / 100
 730 ms 235816 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=200010, inf=2e9;

int m, n;
struct pt2{
    int x, y;
    bool operator < (const pt2 & p) const {
        return x<p.x || (x==p.x && y<p.y);
    }
};

struct pt3{
    int x, y, z;
} P[MX];

struct stair_st {
    set<pt2> S;
    void init(){
        S.insert({0,inf});
        S.insert({inf,0});
    }
    void put(pt2 &p){
        auto rit=S.upper_bound(p);
        if(prev(rit)->y < p.y) return;
        while(rit->y >= p.y) S.erase(rit++);
        S.insert(p);
    }
    bool valid(pt2 &p){
        auto rit=S.upper_bound(p); rit--;
        if(rit->y <= p.y) return true;
        return false;
    }
} Stair[MX];

void solve3(){

    vector<int> X;
    for(int i=1; i<=n; i++) X.push_back(P[i].x);
    sort(X.begin(), X.end());
    X.resize(unique(X.begin(), X.end())-X.begin());
    for(int i=1; i<=n; i++) P[i].x=lower_bound(X.begin(), X.end(), P[i].x)-X.begin()+1;

    vector<int> Y;
    for(int i=1; i<=n; i++) Y.push_back(P[i].y);
    sort(Y.begin(), Y.end());
    Y.resize(unique(Y.begin(), Y.end())-Y.begin());
    for(int i=1; i<=n; i++) P[i].y=lower_bound(Y.begin(), Y.end(), P[i].y)-Y.begin()+1;

    vector<int> Z;
    for(int i=1; i<=n; i++) Z.push_back(P[i].z);
    sort(Z.begin(), Z.end());
    Z.resize(unique(Z.begin(), Z.end())-Z.begin());
    for(int i=1; i<=n; i++) P[i].z=lower_bound(Z.begin(), Z.end(), P[i].z)-Z.begin()+1;

    sort(P+1, P+n+1, [](pt3 &a, pt3 &b){
        return a.z<b.z;
    });

    for(int i=1; i<=n; i++) Stair[i].init();
    Stair[0].S.insert({0,0});
    int ans=0;

    for(int i=1; i<=n; i++){
        pt2 p={P[i].x, P[i].y};
        int s=0, e=n;
        while(s<e){
            int m=(s+e+1)/2;
            if(Stair[m].valid(p)) s=m;
            else e=m-1;
        }
        ans=max(ans, s+1);
        Stair[s+1].put(p);
    }
    cout<<ans;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>m>>n;
    for(int i=1; i<=n; i++) cin>>P[i].x;
    for(int i=1; i<=n; i++) cin>>P[i].y;
    if(m==2) for(int i=1; i<=n; i++) P[i].z=P[i].y;
    else for(int i=1; i<=n; i++) cin>>P[i].z;
    solve3();
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 11640 KB Output is correct
2 Correct 24 ms 11952 KB Output is correct
3 Correct 33 ms 12096 KB Output is correct
4 Correct 24 ms 12332 KB Output is correct
5 Correct 28 ms 12536 KB Output is correct
6 Correct 23 ms 12984 KB Output is correct
7 Correct 24 ms 13056 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 13128 KB Output is correct
2 Correct 26 ms 13420 KB Output is correct
3 Correct 28 ms 13584 KB Output is correct
4 Correct 28 ms 13968 KB Output is correct
5 Correct 28 ms 14360 KB Output is correct
6 Correct 27 ms 14824 KB Output is correct
7 Correct 31 ms 14860 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 11640 KB Output is correct
2 Correct 24 ms 11952 KB Output is correct
3 Correct 33 ms 12096 KB Output is correct
4 Correct 24 ms 12332 KB Output is correct
5 Correct 28 ms 12536 KB Output is correct
6 Correct 23 ms 12984 KB Output is correct
7 Correct 24 ms 13056 KB Output is correct
8 Correct 644 ms 50244 KB Output is correct
9 Correct 555 ms 54300 KB Output is correct
10 Correct 369 ms 58144 KB Output is correct
11 Correct 510 ms 62256 KB Output is correct
12 Correct 486 ms 65876 KB Output is correct
13 Correct 387 ms 69824 KB Output is correct
14 Correct 403 ms 73488 KB Output is correct
15 Correct 476 ms 77488 KB Output is correct
16 Correct 356 ms 81376 KB Output is correct
17 Correct 361 ms 85128 KB Output is correct
18 Correct 352 ms 89140 KB Output is correct
19 Correct 368 ms 92872 KB Output is correct
20 Correct 730 ms 97020 KB Output is correct

Subtask #4
62.0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 13128 KB Output is correct
2 Correct 26 ms 13420 KB Output is correct
3 Correct 28 ms 13584 KB Output is correct
4 Correct 28 ms 13968 KB Output is correct
5 Correct 28 ms 14360 KB Output is correct
6 Correct 27 ms 14824 KB Output is correct
7 Correct 31 ms 14860 KB Output is correct
8 Correct 425 ms 97524 KB Output is correct
9 Correct 480 ms 102200 KB Output is correct
10 Correct 406 ms 111648 KB Output is correct
11 Correct 432 ms 120120 KB Output is correct
12 Correct 625 ms 125956 KB Output is correct
13 Correct 418 ms 127760 KB Output is correct
14 Correct 428 ms 130448 KB Output is correct
15 Correct 436 ms 140300 KB Output is correct
16 Correct 398 ms 145960 KB Output is correct
17 Correct 405 ms 148700 KB Output is correct
18 Correct 545 ms 151776 KB Output is correct
19 Correct 382 ms 157200 KB Output is correct
20 Correct 404 ms 166128 KB Output is correct
21 Correct 386 ms 174936 KB Output is correct
22 Correct 471 ms 175400 KB Output is correct
23 Correct 424 ms 183548 KB Output is correct
24 Correct 381 ms 186128 KB Output is correct
25 Correct 497 ms 193576 KB Output is correct
26 Correct 368 ms 197764 KB Output is correct
27 Correct 604 ms 213052 KB Output is correct
28 Correct 449 ms 215660 KB Output is correct
29 Correct 396 ms 218264 KB Output is correct
30 Correct 482 ms 224148 KB Output is correct
31 Correct 445 ms 226812 KB Output is correct
32 Correct 399 ms 235816 KB Output is correct