oj.uz

Submission #361625

# Submission time Handle Problem Language Result Execution time Memory
361625 2021-01-30T20:43:25 Z gratus907 None (KOI18_matrix) C++17
38 / 100
 4000 ms 392080 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
using pii = pair<int, int>;
void solve_2();
int m, n;
int arr[3][202020];
set <int> s;
const int MAXR = 404040;
const int MAXC = 404040;

char buf[10000011];
int idx, widx;
inline void readint(int & r) {
    r = 0;
    char c = buf[idx++];
    while (c < 33) c = buf[idx++];
    while (c >= 48 && c <= 57) {
        r = r * 10 + (c & 15);
        c = buf[idx++];
    }
}
// max-dynamic-2seg
// msg555 impl, some modifications
struct Dynamic2DSeg
{
    struct Node
    {
        Node (int l, int r, int v = 0) : l(l), r(r), v(v), lc(NULL), rc(NULL){}
        int l, r, v;
        Node *lc, *rc;
    };
    struct RowNode
    {
        RowNode () : lc(NULL), rc(NULL), rowRoot(0, MAXC, 0){}
        Node rowRoot;
        RowNode *lc, *rc;
    };
    RowNode root;
    static void update2(Node *node, int idx, int dt)
    {
        int lo = node -> l;
        int hi = node -> r;
        int mid = (lo + hi) / 2;
        if (lo + 1 == hi)
        {
            node -> v = dt;
            return;
        }
        Node *& next = idx < mid ? node -> lc : node -> rc;
        if (next == NULL)
            next = new Node(idx, idx + 1, dt);
        else if (next -> l <= idx && idx < next -> r)
            update2(next, idx, dt);
        else
        {
            do {
                (idx < mid ? hi : lo) = mid;
                mid = (lo + hi) / 2;
            } while ((idx < mid) == (next->l < mid));
            Node * nnode = new Node(lo, hi);
            (next->l < mid ? nnode->lc : nnode->rc) = next;
            next = nnode;

            update2(nnode, idx, dt);
        }
        node -> v = max(node->lc?node->lc->v:0, node->rc?node->rc->v:0);
    }
    static void update1(RowNode * node, int lo, int hi, int ridx, int idx, int dt)
    {
        int mid = (lo + hi) / 2;
        if (lo + 1 == hi)
            update2(&node -> rowRoot, idx, dt);
        else
        {
            RowNode *& nnode = ridx < mid ? node -> lc : node -> rc;
            (ridx < mid ? hi : lo) = mid;
            if (nnode == NULL)
                nnode = new RowNode();
            update1(nnode, lo, hi, ridx, idx, dt);
            dt = max(node->lc ? query2(&node->lc->rowRoot, idx, idx + 1) : 0,
                     node->rc ? query2(&node->rc->rowRoot, idx, idx + 1) : 0);
            update2(&node->rowRoot, idx, dt);
        }
    }
    static int query2(Node *node, int a, int b)
    {
        if (node == NULL || b <= node -> l || node -> r <= a)
            return 0;
        else if (a <= node -> l && node -> r <= b)
            return node -> v;
        return max(query2(node->lc, a, b), query2(node->rc, a, b));
    }
    static int query1(RowNode *node, int lo, int hi, int a1, int b1, int a2, int b2)
    {
        if (node == NULL || b1 <= lo || hi <= a1)
            return 0;
        else if (a1 <= lo && hi <= b1)
            return query2(&node->rowRoot, a2, b2);
        int mid = (lo + hi) / 2;
        return max(query1(node->lc, lo, mid, a1, b1, a2, b2),
                   query1(node->rc, mid, hi, a1, b1, a2, b2));
    }
    void update(int x, int y, int dt)
    {
        update1(&root, 0, MAXR, x, y, dt);
    }
    int query(int x1, int y1, int x2, int y2)
    {
        return query1(&root, 0, MAXR, x1, x2 + 1, y1, y2 + 1);
    }
} DSEG;

void solve_3()
{
    vector <pair<int, pii>> v;
    for (int i = 0; i < n; i++)
        v.push_back({arr[0][i], {arr[1][i], arr[2][i]}});
    sort(all(v));
    vector <int> ans(n, 0);
    for (int i = n-1; i >= 0; i--)
    {
        int cx = v[i].second.first;
        int cy = v[i].second.second;
        ans[i] = DSEG.query(cx+1, cy+1, 1e9+1, 1e9+1) + 1;
        DSEG.update(cx, cy, ans[i]);
    }
    int r = 0;
    for (auto it:ans)
        r = max(it, r);
    cout << r << '\n';
}

vector <int> compress;
int32_t main()
{
    fread(buf, 1, 6262626, stdin);
    readint(m); readint(n);
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            readint(arr[i][j]);
            if (i)
                compress.push_back(arr[i][j]);
        }
    }
    sort(all(compress));
    compress.erase(unique(all(compress)), compress.end());
    for (int i = 1; i < m; i++)
        for (int j = 0; j < n; j++)
            arr[i][j] = lower_bound(all(compress), arr[i][j]) - compress.begin();
    if (m == 2)
        solve_2();
    else solve_3();
}


void solve_2()
{
    vector <pii> v;
    for (int i = 0; i < n; i++)
        v.push_back({arr[0][i], arr[1][i]});
    sort(all(v));
    vector <int> vv;
    for (int i = 0; i < n; i++)
        vv.push_back(v[i].second);
    set <int> :: iterator it;
    for (int i = 0; i < n; i++)
    {
        s.insert(vv[i]);
        it = s.upper_bound(vv[i]);
        if (it != s.end())
            s.erase(it);
    }
    cout << s.size() << '\n';
}

Compilation message

matrix.cpp: In constructor 'Dynamic2DSeg::RowNode::RowNode()':
matrix.cpp:43:23: warning: 'Dynamic2DSeg::RowNode::rc' will be initialized after [-Wreorder]
   43 |         RowNode *lc, *rc;
      |                       ^~
matrix.cpp:42:14: warning:   'Dynamic2DSeg::Node Dynamic2DSeg::RowNode::rowRoot' [-Wreorder]
   42 |         Node rowRoot;
      |              ^~~~~~~
matrix.cpp:41:9: warning:   when initialized here [-Wreorder]
   41 |         RowNode () : lc(NULL), rc(NULL), rowRoot(0, MAXC, 0){}
      |         ^~~~~~~
matrix.cpp: In function 'int32_t main()':
matrix.cpp:143:10: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  143 |     fread(buf, 1, 6262626, stdin);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 876 KB Output is correct
2 Correct 5 ms 876 KB Output is correct
3 Correct 5 ms 876 KB Output is correct
4 Correct 5 ms 876 KB Output is correct
5 Correct 6 ms 876 KB Output is correct
6 Correct 5 ms 1260 KB Output is correct
7 Correct 5 ms 1004 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 20012 KB Output is correct
2 Correct 61 ms 19992 KB Output is correct
3 Correct 107 ms 20140 KB Output is correct
4 Correct 130 ms 20024 KB Output is correct
5 Correct 78 ms 19884 KB Output is correct
6 Correct 51 ms 19884 KB Output is correct
7 Correct 127 ms 19884 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 876 KB Output is correct
2 Correct 5 ms 876 KB Output is correct
3 Correct 5 ms 876 KB Output is correct
4 Correct 5 ms 876 KB Output is correct
5 Correct 6 ms 876 KB Output is correct
6 Correct 5 ms 1260 KB Output is correct
7 Correct 5 ms 1004 KB Output is correct
8 Correct 115 ms 9952 KB Output is correct
9 Correct 120 ms 9952 KB Output is correct
10 Correct 111 ms 11100 KB Output is correct
11 Correct 90 ms 9952 KB Output is correct
12 Correct 111 ms 10080 KB Output is correct
13 Correct 137 ms 13676 KB Output is correct
14 Correct 111 ms 9952 KB Output is correct
15 Correct 86 ms 9952 KB Output is correct
16 Correct 137 ms 18268 KB Output is correct
17 Correct 137 ms 13660 KB Output is correct
18 Correct 111 ms 12892 KB Output is correct
19 Correct 111 ms 10204 KB Output is correct
20 Correct 115 ms 9952 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 20012 KB Output is correct
2 Correct 61 ms 19992 KB Output is correct
3 Correct 107 ms 20140 KB Output is correct
4 Correct 130 ms 20024 KB Output is correct
5 Correct 78 ms 19884 KB Output is correct
6 Correct 51 ms 19884 KB Output is correct
7 Correct 127 ms 19884 KB Output is correct
8 Correct 1658 ms 392080 KB Output is correct
9 Correct 2143 ms 389368 KB Output is correct
10 Correct 1233 ms 392044 KB Output is correct
11 Correct 1028 ms 392024 KB Output is correct
12 Correct 2435 ms 384268 KB Output is correct
13 Correct 1423 ms 392012 KB Output is correct
14 Correct 3212 ms 391636 KB Output is correct
15 Correct 1020 ms 392068 KB Output is correct
16 Correct 1018 ms 391944 KB Output is correct
17 Correct 2077 ms 392060 KB Output is correct
18 Execution timed out 4113 ms 307236 KB Time limit exceeded
19 Halted 0 ms 0 KB -