oj.uz

Submission #427775

# Submission time Handle Problem Language Result Execution time Memory
427775 2021-06-14T22:09:46 Z Chaska Exhibition (JOI19_ho_t2) C++11
0 / 100
 1 ms 420 KB 
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef pair<int,int> i2;
const int N = 3e5+5;
int n,m,b[N];
i2 ax[N];
int cnt,res,x,st[4*N],a[N];
set<int> s;
map<int,int> h;
void get(int no,int in,int fin,int val)
{
    if (fin < val) return;
    if(val <= in) {
        x = max(x,st[no]);
        return;
    }
    int mid = (in+fin)/2;
    get(no*2+1,in,mid,val);
    get(no*2+2,mid+1,fin,val);
    return;
}
void upd(int no,int in,int fin,int pos)
{
    if (fin < pos || in > pos) return;
    if (in == fin) {
        st[no] = max(st[no],x);
        return;
    }
    int mid = (in+fin)/2;
    upd(no*2+1,in,mid,pos);
    upd(no*2+2,mid+1,fin,pos);
    st[no] = max(st[no*2+1],st[no*2+2]);
    return;
}
int main()
{
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> m;
    for (int i=0;i<n;i++) cin >> ax[i].S >> ax[i].F;
    for (int i=0;i<m;i++) cin >> b[i];
   sort(ax,ax+n);
    for (int i=0;i<n;i++){ a[i] = ax[i].S; s.insert(a[i]); }
    for (int i=0;i<m;i++){s.insert(b[i]);}
    for (int u : s) h[u] = ++cnt;
    for (int i=0;i<n;i++) a[i] = h[a[i]];
    for (int i=0;i<m;i++) b[i] = h[b[i]];
     
    sort(b,b+m);
   // for (int i=0;i<n;i++)  cout<< a[i ] << " ";
    for (int i=n-1;i>=0;i--) {
        x = 0;
        get(0,1,cnt,a[i]);
        x++;
        if (x>m) {
            x=m;
            upd(0,1,cnt,a[i]);
            //cout << x << " ";
        } else {
            int p = b[m-x];
            if (a[i] > p) {
                x--;
                upd(0,1,cnt,a[i]);
            } else {
                upd(0,1,cnt,a[i]);
            }
           // cout << x << " ";
        }
    }
    cout << st[0];
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 420 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 420 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 420 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -