Cod sursa(job #2921558)

Utilizator albertaizicAizic Albert albertaizic Data 31 august 2022 17:38:58
Problema Lupul Urias si Rau Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX_N 200000
pair <int,int> poz[MAX_N+1];
int heap[MAX_N+1];
int j;
bool cmp(const pair<int,int>& a, const pair<int,int>& b) {
  return a.first<b.first;
}
void add(int i){
  while(i && heap[(i-1)/2]<heap[i]){
    swap(heap[i],heap[(i-1)/2]);
    i=(i-1)/2;
  }
}

void down(int i){
  int left,right,mmax;

  mmax=i;
  left=i*2+1, right=i*2+2;

  if(left<j && heap[left]>heap[mmax])
    mmax=left;
  if(right<j && heap[right]>heap[mmax])
    mmax=right;

  if(i!=mmax){
    swap(heap[i],heap[mmax]);
    down(mmax);
  }

}

void er(){
  heap[0]=heap[--j];
  down(0);
}
int main(){
    FILE *fin,*fout;
    int n,i,x,l,s;
    fin=fopen("heapuri.in","r");
    fout=fopen("heapuri.out","w");
    fscanf(fin,"%d%d%d",&n,&x,&l);
    for(i=0;i<n;i++){
      fscanf(fin,"%d%d",&poz[i].first,&poz[i].second);

    }

    sort(poz,poz+n,cmp);
    j=s=0;
    int jj=0;
    for(i=x%l;i<=x;i+=l){
      while(poz[jj].first<=i){
        heap[j]=poz[jj].second;
        add(j);
        j++;
        jj++;
      }
      s+=heap[0];
      er();
    }
    fprintf(fout,"%d\n",s);
    fclose(fout);
    return 0;
}