oj.uz

Submission #133037

# Submission time Handle Problem Language Result Execution time Memory
133037 2019-07-20T05:48:34 Z dantoh000 Exhibition (JOI19_ho_t2) C++14
0 / 100
 2 ms 632 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
bool cmp(ii a, ii b){
    if (a.second != b.second) return a.second < b.second;
    else return a.first<b.first;
}
int fw[100005];
int n;
void up(int x, int nv){
    //printf("up %d %d\n",x,nv);
    while (x <= n){
        fw[x] = max(fw[x],nv);
        x += (x)&(-x);
    }
}
int rmq(int x){
    //printf("quering %d\n",x);
    int ans = 0;
    while (x){
        ans = max(ans,fw[x]);
        x -= (x)&(-x);
    }
    return ans;
}
int main(){
    memset(fw,0,sizeof(fw));
    int m;
    scanf("%d%d",&n,&m);
    ii a[n];
    for (int i = 0; i < n; i++){
        scanf("%d%d",&a[i].first,&a[i].second);
    }
    sort(a,a+n,cmp);
    int b[m];
    for (int i =0 ; i<m; i++) scanf("%d",&b[i]);
    sort(b,b+m);
    ii h[n];
    for (int i = 0; i < n; i++) h[i] = ii(a[i].first,i+1);
    sort(h,h+n);
    int ans[n+1]; memset(ans,0,sizeof(ans));
    int cur = 0;
    for (int i = 0; i < m; i++){
        for (int j = 0; j < cur; j++){
            ans[h[j].second] = rmq(h[j].second-1) + 1;
        }
        while (h[cur].first <= b[i] && cur < n){
            ans[h[cur].second] = rmq(h[cur].second-1) + 1;
            cur++;
        }
        for (int last = 0; last < cur; last++){
            up(h[last].second,ans[h[last].second]);
            last++;
        }
        for (int j = 1; j <= n; j++){
            //printf("%d ",ans[j]);
        }
        //printf("\n");
    }
    int kk = 0;
    for (int i = 1; i <= n;i++ ){
        kk = max(ans[i],kk);
    }
    printf("%d",kk);


}

Compilation message

joi2019_ho_t2.cpp: In function 'int main()':
joi2019_ho_t2.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
joi2019_ho_t2.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a[i].first,&a[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t2.cpp:36:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i =0 ; i<m; i++) scanf("%d",&b[i]);
                               ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Incorrect 2 ms 632 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Incorrect 2 ms 632 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Incorrect 2 ms 632 KB Output isn't correct
3 Halted 0 ms 0 KB -