Advertisement
Guest User

Untitled

a guest
Sep 15th, 2016
49
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.56 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <assert.h>
  3. #include <iostream>
  4. #include <map>
  5. #define MAXN 100000
  6. using namespace std;
  7.  
  8. bool controlla_carica(int carica, map<int, bool> schema, int M) {
  9.     //cout << "Controllo " << carica << endl;
  10.     for (int i = 0; i < M; i++) {
  11.         if (schema[i]) carica++;
  12.         else carica--;
  13.         if (carica <= 0) {
  14.             return false;
  15.         }
  16.     }
  17.     return true;
  18. }
  19. int ricarica(int N, int M, int A[], int B[]) {
  20.     map<int, bool> schema;
  21.     for (int i = 0; i < N; i++) {
  22.         for (int j = A[i]; j <= B[i]; j++) {
  23.             schema[j-1] = true;
  24.         }
  25.     }
  26.  
  27.     int first_carica, last_carica;
  28.     int carica = 1;
  29.     while (!controlla_carica(carica, schema, M)) {
  30.         carica *= 2;
  31.     }
  32.     first_carica = carica / 2;
  33.     last_carica = carica - 1;
  34.     while (first_carica < last_carica) {
  35.         int middle = first_carica + (last_carica - first_carica) / 2 + 1;
  36.         if (!controlla_carica(middle, schema, M)) {
  37.             first_carica = middle;
  38.         }
  39.         else {
  40.             last_carica = middle - 1;
  41.         }
  42.     }
  43.     first_carica++;
  44.     //cout << first_carica << endl;
  45.     return first_carica;
  46.  
  47. }
  48.  
  49.  
  50.  
  51. int A[MAXN], B[MAXN];
  52.  
  53. int main() {
  54.     FILE *fr, *fw;
  55.     int N, M, i;
  56.  
  57.     fr = fopen("input.txt", "r");
  58.     fw = fopen("output.txt", "w");
  59.     assert(2 == fscanf(fr, "%d %d", &N, &M));
  60.     for(i=0; i<N; i++)
  61.         assert(2 == fscanf(fr, "%d %d", &A[i], &B[i]));
  62.  
  63.     fprintf(fw, "%d\n", ricarica(N, M, A, B));
  64.     fclose(fr);
  65.     fclose(fw);
  66.     return 0;
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement