fork download
copy 
  1. // hloya template v19
  2.  
  3. #include <bits/stdc++.h>
  4. #include <valarray>
  5. using namespace std;
  6.  
  7. bool dbg = 0;
  8.  
  9. // clock_t start_time = clock();
  10. #define current_time fixed<<setprecision(6)<<(ld)(clock()-start_time)/CLOCKS_PER_SEC
  11.  
  12. #define f first
  13. #define s second
  14. #define mp make_pair
  15. #define pb push_back
  16. #define all(x) (x).begin(), (x).end()
  17.  
  18. #define ll unsigned int
  19. #define ld long double
  20. #define pii pair<int,int>
  21.  
  22. #define files1 freopen("input.txt","r",stdin)
  23. #define files2 freopen("magic.out","w",stdout)
  24. #define files files1;files2
  25. #define fast_io ios_base::sync_with_stdio(0);cin.tie(0)
  26.  
  27. #define endl '\n'
  28. #define ln(i,n) " \n"[(i) == (n) - 1]
  29.  
  30. void bad(string mes = "Impossible"){cout << mes;exit(0);}
  31.  
  32. template<typename T>
  33. string bin(T x, int st = 2){
  34.     string ans = "";
  35.     while (x > 0){
  36.         ans += char('0' + x % st);
  37.         x /= st;
  38.     }
  39.     reverse(ans.begin(), ans.end());
  40.     return ans.empty() ? "0" : ans;
  41. }
  42.  
  43. template<typename T>
  44. T input(){
  45.     T ans = 0, m = 1;
  46.     char c = ' ';
  47.  
  48.     while (!((c >= '0' && c <= '9') || c == '-')) {
  49.         c = getchar();
  50.     }
  51.  
  52.     if (c == '-')
  53.         m = -1, c = getchar();
  54.     while (c >= '0' && c <= '9'){
  55.         ans = ans * 10 + (c - '0'), c = getchar();
  56.     }
  57.     return ans * m;
  58. }
  59.  
  60. template<typename T> void read(T& a) { a = input<T>(); }
  61. template<typename T> void read(T& a, T& b) { read(a), read(b); }
  62. template<typename T> void read(T& a, T& b, T& c) { read(a, b), read(c); }
  63. template<typename T> void read(T& a, T& b, T& c, T& d) { read(a, b), read(c, d); }
  64.  
  65. void reads(string & s) {
  66.     string ans = "";
  67.     char c = endl;
  68.     while (c == endl || c == ' ')
  69.         c = getchar();
  70.     while (c != endl && c != ' ' && c)
  71.         ans += c, c = getchar();
  72.     s = ans;
  73. }
  74.  
  75. const int inf = 1e9;
  76. const long double eps = 1e-12;
  77. const int maxn = 3e2 + 10, base = 1e9 + 7;
  78. const ll llinf = 1e18 + 5;
  79.  
  80. template<typename T>
  81. T binpow(T n, T s)
  82. {
  83.     if (s <= 0)
  84.         return 1LL;
  85.     if (s % 2 == 0){
  86.         T b = binpow(n, s / 2);
  87.         return ( 1LL * b * b ) % base;
  88.     } else {
  89.         return (1LL* binpow(n, s - 1) * n) % base;
  90.     }
  91. }
  92.  
  93. int test;
  94.  
  95. bool solve() {
  96.     int l, n;
  97.     read(l, n);
  98.     if (!l && !n)
  99.         return false;
  100.     vector<pair<int, int> > a(n);
  101.  
  102.     for (int i = 0; i < n; i++) {
  103.         int x, r;
  104.         read(x, r);
  105.         a[i] = mp(max(0, x - r), min(l, x + r));
  106.     }
  107.  
  108.     sort(all(a));
  109.  
  110.     int fs = 0;
  111.     int ans = 0, curMx = -1;
  112.     for (int i = 0; i < n;) {
  113.         if (a[i].f <= fs) {
  114.             curMx = max(curMx, a[i].s);
  115.             i++;
  116.         } else {
  117.             if (curMx <= fs) {
  118.                 puts("-1");
  119.                 return true;
  120.             }
  121.             fs = curMx;
  122.             ans++;
  123.             curMx = -1;
  124.         }
  125.     }
  126.  
  127.     if (fs != l) {
  128.         if (curMx <= fs) {
  129.             puts("-1");
  130.             return true;
  131.         }
  132.         fs = curMx;
  133.         ans++;
  134.     }
  135.     if (fs != l) {
  136.         puts("-1");
  137.         return true;
  138.     }
  139.  
  140.     printf("%d\n", n - ans);
  141.     return true;
  142. }
  143.  
  144. int main() {
  145.     while (solve()) {}
  146. }
Time limit exceeded #stdin #stdout 5s 3472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/90ZbjN
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!