oj.uz

Submission #361618

# Submission time Handle Problem Language Result Execution time Memory
361618 2021-01-30T20:29:38 Z gratus907 None (KOI18_matrix) C++17
38 / 100
 4000 ms 634844 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 = 1000000007;
const int MAXC = 1000000007;

// max-dynamic-2seg
// msg555 impl, some modifications
int agg(int a, int b) {return max(a, b);}
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 = agg(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 = agg(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 agg(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 agg(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';
}

int32_t main()
{
    usecppio
    cin >> m >> n;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> arr[i][j];
    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:33:23: warning: 'Dynamic2DSeg::RowNode::rc' will be initialized after [-Wreorder]
   33 |         RowNode *lc, *rc;
      |                       ^~
matrix.cpp:32:14: warning:   'Dynamic2DSeg::Node Dynamic2DSeg::RowNode::rowRoot' [-Wreorder]
   32 |         Node rowRoot;
      |              ^~~~~~~
matrix.cpp:31:9: warning:   when initialized here [-Wreorder]
   31 |         RowNode () : lc(NULL), rc(NULL), rowRoot(0, MAXC, 0){}
      |         ^~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 5 ms 876 KB Output is correct
6 Correct 6 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 84 ms 32692 KB Output is correct
2 Correct 73 ms 32812 KB Output is correct
3 Correct 112 ms 32724 KB Output is correct
4 Correct 146 ms 32300 KB Output is correct
5 Correct 91 ms 32684 KB Output is correct
6 Correct 64 ms 32684 KB Output is correct
7 Correct 145 ms 32428 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 5 ms 876 KB Output is correct
6 Correct 6 ms 1260 KB Output is correct
7 Correct 5 ms 1004 KB Output is correct
8 Correct 104 ms 5988 KB Output is correct
9 Correct 102 ms 5860 KB Output is correct
10 Correct 100 ms 7012 KB Output is correct
11 Correct 74 ms 5860 KB Output is correct
12 Correct 100 ms 5860 KB Output is correct
13 Correct 126 ms 9444 KB Output is correct
14 Correct 101 ms 5988 KB Output is correct
15 Correct 74 ms 5860 KB Output is correct
16 Correct 134 ms 14180 KB Output is correct
17 Correct 129 ms 9444 KB Output is correct
18 Correct 101 ms 8804 KB Output is correct
19 Correct 100 ms 5988 KB Output is correct
20 Correct 106 ms 5868 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 32692 KB Output is correct
2 Correct 73 ms 32812 KB Output is correct
3 Correct 112 ms 32724 KB Output is correct
4 Correct 146 ms 32300 KB Output is correct
5 Correct 91 ms 32684 KB Output is correct
6 Correct 64 ms 32684 KB Output is correct
7 Correct 145 ms 32428 KB Output is correct
8 Correct 2149 ms 629212 KB Output is correct
9 Correct 2440 ms 626304 KB Output is correct
10 Correct 1630 ms 629468 KB Output is correct
11 Correct 1398 ms 634844 KB Output is correct
12 Correct 2748 ms 625500 KB Output is correct
13 Correct 1830 ms 634716 KB Output is correct
14 Execution timed out 4032 ms 634308 KB Time limit exceeded
15 Halted 0 ms 0 KB -