oj.uz

Submission #361613

# Submission time Handle Problem Language Result Execution time Memory
361613 2021-01-30T20:16:21 Z gratus907 None (KOI18_matrix) C++17
38 / 100
 2388 ms 634708 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){}
        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){}
      |         ^~~~~~~

Subtask #1
14.0 / 14.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 32428 KB Output is correct
2 Correct 72 ms 32428 KB Output is correct
3 Correct 119 ms 32428 KB Output is correct
4 Correct 152 ms 32044 KB Output is correct
5 Correct 96 ms 32428 KB Output is correct
6 Correct 64 ms 32428 KB Output is correct
7 Correct 151 ms 32160 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 548 KB Output is correct
2 Correct 5 ms 620 KB Output is correct
3 Correct 5 ms 620 KB Output is correct
4 Correct 5 ms 748 KB Output is correct
5 Correct 5 ms 620 KB Output is correct
6 Correct 6 ms 1004 KB Output is correct
7 Correct 5 ms 748 KB Output is correct
8 Correct 106 ms 5476 KB Output is correct
9 Correct 101 ms 5348 KB Output is correct
10 Correct 113 ms 6500 KB Output is correct
11 Correct 76 ms 5348 KB Output is correct
12 Correct 100 ms 5340 KB Output is correct
13 Correct 127 ms 8932 KB Output is correct
14 Correct 100 ms 5348 KB Output is correct
15 Correct 74 ms 5348 KB Output is correct
16 Correct 132 ms 13668 KB Output is correct
17 Correct 126 ms 8932 KB Output is correct
18 Correct 99 ms 8292 KB Output is correct
19 Correct 101 ms 5348 KB Output is correct
20 Correct 103 ms 5348 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 32428 KB Output is correct
2 Correct 72 ms 32428 KB Output is correct
3 Correct 119 ms 32428 KB Output is correct
4 Correct 152 ms 32044 KB Output is correct
5 Correct 96 ms 32428 KB Output is correct
6 Correct 64 ms 32428 KB Output is correct
7 Correct 151 ms 32160 KB Output is correct
8 Correct 2148 ms 629080 KB Output is correct
9 Correct 2388 ms 625884 KB Output is correct
10 Incorrect 1628 ms 634708 KB Output isn't correct
11 Halted 0 ms 0 KB -