oj.uz

답안 #1026395

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1026395 2024-07-18T04:20:14 Z Mardonbekhazratov 송신탑 (IOI22_towers) C++17
4 / 100
 4000 ms 4672 KB 
#include "towers.h"

#include <vector>
#include <algorithm>
#include <iostream>
#include <map>
#include <set>

using namespace std;

struct SegTree{
    int N;
    vector<int>tree;

    int merge(int a,int b){
        return max(a,b);
    }

    void build(int n){
        N=1;
        while(N<n) N<<=1;
        
        tree.assign(2*N,0);
    }

    void update(int v,int l,int r,int id,int x){
        if(r-l==1){
            tree[v]=x;
            return;
        }
        int mid=(l+r)/2;
        if(id<mid) update(v<<1,l,mid,id,x);
        else update(v<<1|1,mid,r,id,x);
        tree[v]=merge(tree[v<<1],tree[v<<1|1]);
    }

    void update(int id,int x){
        return update(1,0,N,id,x);
    }

    int get(int v,int l,int r,int ql,int qr){
        if(ql>=r || l>=qr) return 0;
        if(l>=ql && qr>=r) return tree[v];

        int mid=(l+r)/2;
        return merge(get(v<<1,l,mid,ql,qr),get(v<<1|1,mid,r,ql,qr));
    }

    int get(int l,int r){
        if(r<=l) return 0;
        return get(1,0,N,l,r);
    }
};

int n,k;
vector<int>h;
bool su1=true;


void init(int N, std::vector<int> H) {
    n=N;
    h=H;
    k=0;
    bool ok=true;
    for(int i=1;i<n;i++){
        if(h[i]>h[i-1] && ok) k=i;
        else{
            if(h[i]>h[i-1]) su1=false;
            ok=false;
        }
    }
}

int max_towers(int L, int R, int D) {
    if(su1){
        if(L<k && R>k && h[k]-D>=h[L] && h[k]-D>=h[R]) return 2;
        return 1;
    }
    vector<int>a,dp(R-L+1);
    dp[0]=1;
    for(int i=L;i<=R;i++){
        a.push_back(h[i]);
    }
    
    // map<int,int>mp;
    vector<int>b=a;
    sort(b.begin(),b.end());
    int c=b.size();
    // for(int x:b) m[x]=c++;
    SegTree S1,S2;
    S1.build(c+2);
    S2.build(c+2);
    
    int ans=1,mx=0;
    S1.update(0,1);
    for(int i=1;i<a.size();i++){
        int pos=lower_bound(b.begin(),b.end(),a[i]+D)-b.begin();
        dp[i]=S2.get(pos,c+2);
        dp[i]++;
        ans=max(ans,dp[i]);
        int pos2=lower_bound(b.begin(),b.end(),a[i])-b.begin();
        S1.update(pos2,dp[i]);
        int pos1=lower_bound(b.begin(),b.end(),a[i]-D+1)-b.begin();
        S2.update(pos2,S1.get(0,pos1));
        // cout<<dp[i]<<' ';
    }
    return ans;
}

Compilation message

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:96:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for(int i=1;i<a.size();i++){
      |                 ~^~~~~~~~~
towers.cpp:94:15: warning: unused variable 'mx' [-Wunused-variable]
   94 |     int ans=1,mx=0;
      |               ^~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 293 ms 1112 KB Output is correct
2 Correct 598 ms 1368 KB Output is correct
3 Correct 666 ms 1368 KB Output is correct
4 Correct 671 ms 1368 KB Output is correct
5 Correct 607 ms 1368 KB Output is correct
6 Correct 637 ms 1368 KB Output is correct
7 Correct 592 ms 1368 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '13', found: '14'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '13', found: '14'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4025 ms 4672 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4040 ms 1628 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '13', found: '14'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 293 ms 1112 KB Output is correct
2 Correct 598 ms 1368 KB Output is correct
3 Correct 666 ms 1368 KB Output is correct
4 Correct 671 ms 1368 KB Output is correct
5 Correct 607 ms 1368 KB Output is correct
6 Correct 637 ms 1368 KB Output is correct
7 Correct 592 ms 1368 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '13', found: '14'
12 Halted 0 ms 0 KB -