Submission #1255331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255331		tiago	Global Warming (CEOI18_glo)	C++20	100 / 100	744 ms	55368 KiB

glo

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = (1e5 + 10)*4;

int seg[4*maxn];
int seg_semmuda[4*maxn];

void definir(int x, int posi, int ld, int rd, int idx, int qual){
    if(ld == rd){
        if(qual == 0) seg[idx] = max(seg[idx],x);
        else seg_semmuda[idx] = max(seg_semmuda[idx],x);
        return;
    }
    int meio = (ld+rd)/2;
    if(posi <= meio) definir(x,posi,ld,meio,idx*2,qual);
    else if(posi > meio) definir(x,posi,meio+1,rd,idx*2+1,qual);

    if(qual == 0) seg[idx] = max(seg[idx*2],seg[idx*2+1]);
    else seg_semmuda[idx] = max(seg_semmuda[idx*2],seg_semmuda[idx*2+1]);
}

int achar(int l, int r, int ld, int rd, int idx, int qual){
    if(ld >= l and rd <= r){
        if(qual == 0) return seg[idx];
        else return seg_semmuda[idx];
    }
    if(ld > r or rd < l) return 0;
    int meio = (ld+rd)/2;
    return max(achar(l,r,ld,meio,idx*2,qual),achar(l,r,meio+1,rd,idx*2+1,qual));
}

signed main(){
    memset(seg,0,sizeof(seg));
    memset(seg_semmuda,0,sizeof(seg_semmuda));
    int n,d; cin >> n >> d;
    map<int,int> compre;
    int aux;
    vector<int> v;
    vector<int> ordem;
    for(int i = 1; i <= n; i++){
        cin >> aux;
        v.push_back(aux);
        ordem.push_back(aux); ordem.push_back(aux+d);
    }
    sort(ordem.begin(),ordem.end());
    int atu = 1;
    for(int i = 0; i < (int)ordem.size(); i++){
        if(compre.find(ordem[i]) == compre.end()){
            compre[ordem[i]] = atu;
            atu++;
        }
    }
    int resul = 0;
    for(int i = 0; i < n; i++){
        aux = v[i];
        int puloantigo = achar(1,compre[aux]-1,1,2*n,1,0) + 1;
        int pulonovo = achar(1,compre[aux+d]-1,1,2*n,1,1) + 1;
        int sempulo = achar(1,compre[aux]-1,1,2*n,1,1) + 1;
        int maior = max(puloantigo,pulonovo);
        resul = max(maior,resul);
        definir(maior,compre[aux],1,2*n,1,0);
        definir(sempulo,compre[aux],1,2*n,1,1);
        //cout << endl;
        //cout << aux << endl;
        //cout << puloantigo << " " << pulonovo << " " << sempulo << endl;
    }
    cout << resul;
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25