oj.uz

Submission #62779

# Submission time Handle Problem Language Result Execution time Memory
62779 2018-07-30T03:30:42 Z jjwdi0 None (KOI18_matrix) C++11
29 / 100
 160 ms 3296 KB 
#include <bits/stdc++.h>
#define ROOT 450
using namespace std;
using pr = pair<int, int>;
using tr = pair<int, pr>;
using ll = long long;

int R, N, ans;
pr A[200005];
tr B[200005];
vector<int> v;
int comp[200005], comp_y[200005];
vector<int> comp2[ROOT];

struct seg_tree {
    int tree[ROOT*4], base;
    void init(int x) { for(base=1; base<x; base<<=1); for(int i=1; i<=base*2; i++) tree[i] = 0; }
    void update(int x, int y) {
        x += base - 1;
        tree[x] = y, x /= 2;
        while(x) tree[x] = max(tree[x*2], tree[x*2+1]), x /= 2;
    }
    int RMQ(int s, int e) {
        s += base - 1, e += base - 1;
        int res = 0;
        while(s < e) {
            if(s & 1) res = max(res, tree[s++]);
            if(!(e & 1)) res = max(res, tree[e--]);
            s >>= 1, e >>= 1;
        }
        if(s == e) res = max(res, tree[s]);
        return res;
    }
} S[ROOT];

vector<tr> bucket[ROOT];

int main() {
    scanf("%d %d", &R, &N);
    if(R == 2) {
        for(int i=1; i<=N; i++) scanf("%d", &A[i].first);
        for(int i=1; i<=N; i++) scanf("%d", &A[i].second);
        sort(A+1, A+N+1);
        for(int i=1; i<=N; i++) {
            auto it = lower_bound(v.begin(), v.end(), A[i].second);
            if(it == v.end()) v.push_back(A[i].second);
            else *it = A[i].second;
        }
        printf("%d\n", v.size());
    }
    else {
        for(int i=0; i<=N/ROOT; i++) S[i].init(ROOT + 1);
        for(int i=1; i<=N; i++) scanf("%d", &B[i].first);
        for(int i=1; i<=N; i++) scanf("%d", &B[i].second.first);
        for(int i=1; i<=N; i++) scanf("%d", &B[i].second.second);
        sort(B+1, B+N+1);
        for(int i=1; i<=N; i++) comp[i] = B[i].second.first;
        sort(comp+1, comp+N+1);
        for(int i=1; i<=N; i++) B[i].second.first = (int)( lower_bound(comp+1, comp+N+1, B[i].second.first) - comp );
        for(int i=1; i<=N; i++) comp[i] = B[i].second.second;
        sort(comp+1, comp+N+1);
        for(int i=1; i<=N; i++) B[i].second.second = (int)( lower_bound(comp+1, comp+N+1, B[i].second.second) - comp );

        int ans = 0;

        for(int i=1; i<=N; i++) comp2[i/ROOT].push_back(B[i].second.second);
        for(int i=0; i<=N/ROOT; i++) sort(comp2[i].begin(), comp2[i].end());
        for(int i=1; i<=N; i++) comp_y[i] = (int)(lower_bound(comp2[i/ROOT].begin(), comp2[i/ROOT].end(), B[i].second.second) - comp2[i/ROOT].begin()) + 1;

        for(int i=1; i<=N; i++) {
            int idx = B[i].second.first / ROOT;
            int mx = 1;
            for(int j=0; j<idx; j++) {
                mx = max(mx, S[j].RMQ(1, (int)(upper_bound(comp2[j].begin(), comp2[j].end(), B[i].second.second) - comp2[j].begin()) ) + 1);
            }
            for(auto it : bucket[idx]) {
                if(it.second.first < B[i].second.first && it.second.second < B[i].second.second) mx = max(mx, it.first + 1);
            }
            bucket[idx].push_back(tr(mx, B[i].second));
            S[idx].update(comp_y[i], mx);
            ans = max(ans, mx);
            printf("%d\n", mx);
        }
        printf("%d\n", ans);
    }
}

Compilation message

matrix.cpp: In function 'int main()':
matrix.cpp:49:32: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
         printf("%d\n", v.size());
                        ~~~~~~~~^
matrix.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &R, &N);
     ~~~~~^~~~~~~~~~~~~~~~~
matrix.cpp:41:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         for(int i=1; i<=N; i++) scanf("%d", &A[i].first);
                                 ~~~~~^~~~~~~~~~~~~~~~~~~
matrix.cpp:42:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         for(int i=1; i<=N; i++) scanf("%d", &A[i].second);
                                 ~~~~~^~~~~~~~~~~~~~~~~~~~
matrix.cpp:53:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         for(int i=1; i<=N; i++) scanf("%d", &B[i].first);
                                 ~~~~~^~~~~~~~~~~~~~~~~~~
matrix.cpp:54:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         for(int i=1; i<=N; i++) scanf("%d", &B[i].second.first);
                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
matrix.cpp:55:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         for(int i=1; i<=N; i++) scanf("%d", &B[i].second.second);
                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 504 KB Output is correct
2 Correct 9 ms 616 KB Output is correct
3 Correct 10 ms 672 KB Output is correct
4 Correct 10 ms 740 KB Output is correct
5 Correct 11 ms 740 KB Output is correct
6 Correct 9 ms 740 KB Output is correct
7 Correct 8 ms 740 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 1096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 504 KB Output is correct
2 Correct 9 ms 616 KB Output is correct
3 Correct 10 ms 672 KB Output is correct
4 Correct 10 ms 740 KB Output is correct
5 Correct 11 ms 740 KB Output is correct
6 Correct 9 ms 740 KB Output is correct
7 Correct 8 ms 740 KB Output is correct
8 Correct 125 ms 2184 KB Output is correct
9 Correct 150 ms 2248 KB Output is correct
10 Correct 119 ms 2504 KB Output is correct
11 Correct 142 ms 2504 KB Output is correct
12 Correct 145 ms 2504 KB Output is correct
13 Correct 132 ms 2916 KB Output is correct
14 Correct 146 ms 2916 KB Output is correct
15 Correct 98 ms 2916 KB Output is correct
16 Correct 109 ms 3296 KB Output is correct
17 Correct 160 ms 3296 KB Output is correct
18 Correct 142 ms 3296 KB Output is correct
19 Correct 132 ms 3296 KB Output is correct
20 Correct 134 ms 3296 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 1096 KB Output isn't correct
2 Halted 0 ms 0 KB -