Submission

[PPPPP][PPPPP][PPPPPPPPPP]

Score: 100

User: Ecir

Problemset: ห้องสมุดเมือง 3M

Language: cpp

Time: 0.004 second

Submitted On: 2025-03-17 20:53:18

#include <bits/stdc++.h>
using namespace std;
using ll=long long int;
#define twod array<ll,2>
int arr[109][2];
int main(){
  ios::sync_with_stdio(0);cin.tie(0);
  int n;cin >> n;
  // int mx=0;;
  int sum=0;
  int l=INT_MAX,r=0;
  for(int i=1;i<=n;i++){
    cin >> arr[i][0] >> arr[i][1];
    r=max(r,arr[i][1]-1);
    l=min(l,arr[i][0]);
    sum+=arr[i][1]-arr[i][0];
  }
  while(l<r){
    int m=(l+r)/2;
    int cnt=0;
    for(int i=1;i<=n;i++){
      if(m>=arr[i][1]){
        cnt+=arr[i][1]-arr[i][0];
      }
      else if(m>=arr[i][0]){
        cnt+=m-arr[i][0]+1;
      }
    }
    if(cnt>=sum/2) r=m;
    else l=m+1;
  }
  cout << l;
  return 0;
}

//    1     5       10                                 50                                                100
//    xxxxxxxxxxxxxxxxxxxxxxxxxxx                       |
//            xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx    |
//                  xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
//                                   xxxxxxxxxxxxxxxxxxx|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
//                                      xxxxxxxxxxxxxxxx|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
//                                         xxxxxxxxxxxxx|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
//                                                xxxxxx|xxxxxxxxxxxxxxxxxxx
//                                                   xxx|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx


// https://firefly.gchan.moe/problemset/c2_ds66_3m



// https://cp-algorithms.com/string/string-hashing.html


// Rabin-Karp

// https://open.kattis.com/problems/longestcommonsubstring
// https://open.kattis.com/problems/buzzwords //หาคำซ้ำ
// https://vjudge.net/contest/413733#problem/L //จำนวoนคำที่ต่างกันทั้งหมด

// hard
// https://leetcode.com/problems/longest-duplicate-substring/description/  //คำซ้ำ
// https://open.kattis.com/problems/repeatedsubstrings  //คำซ้ำ
// https://cses.fi/problemset/task/2102
// https://cses.fi/problemset/task/2103
// https://cses.fi/problemset/task/2105  //ตัวซ้ำ
// https://cses.fi/problemset/task/1111  //พาลินโดรม


// a*2 b*4 b*8 a*16 c*32
  
// c*2 a*4 b*8 b*16 a*32
  
  
// (a*2 b*4 b*8 a*16)*2
  
// a*4 b*8 b*16 a*32
  
  


//                              0                                     10   11    12
//               |              0 2 4  8  16  32  64  128  256  512 1024 2048  4096
//    10101010101010101010   h  0 2 2 10  10  42  42  170  170  682 682  2730  2730
//      1010101010                                              h[11]-h[1]     2730-2   =2728 /2   =1364                     
//                                                                 h[12]-h[2]    2730-2    =2728 /4  =682 
//     1010101010->682  10   
// Rabin-Karp  

//   A F G H K G  
//   a b c d e   z
//   0 1 2 3     25
  
//   acg  -> 0*31+2*31^2+3*31^3=
//   tgg  -> 1*31+3*31^2+3*31^3
  
  

// Hash  

  

// https://www.hackerrank.com/contests/crack-n-code-january-2022/challenges/compound

// https://www.hackerrank.com/contests/crack-n-code-september-2021/challenges/lumberjack-2



// https://vjudge.net/contest/573027#overview  A,I,J




// คล้ายข้อ codecube_199 Sagittarius A*
// https://judge.yosupo.jp/problem/minimum_spanning_tree

// 18
// 16 dp[16]=0




// https://open.kattis.com/problems/factovisors
// https://open.kattis.com/problems/productdivisors
// https://open.kattis.com/problems/threedigits
// https://open.kattis.com/problems/divisors
// https://open.kattis.com/problems/primalrepresentation;