fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define all(v) v.begin() , v.end()
  5. #define sz(v) int(v.size())
  6. #define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10. typedef pair<int , int> ii;
  11. typedef pair<long long , int> lli;
  12.  
  13. const int maxN = int(4e5)+7;
  14. const int inf = int(1e9)+7;
  15.  
  16. int n , x[maxN] , a[maxN] , b[maxN] , L[maxN] , R[maxN];
  17. vector<int> val , event[2 * maxN];
  18.  
  19. namespace sub1{
  20.     bool check(){
  21.         for (int i = 2 ; i <= n ; i++){
  22.             if (a[i] != a[i - 1] || b[i] != b[i - 1]) return 0;
  23.         }
  24.         return 1;
  25.     }
  26.  
  27.     void solve(){
  28.         if (n == 1){
  29.             cout << "1 -1\n";
  30.         }
  31.         else{
  32.             cout << "2 " << 2 * (n - 1) << "\n";
  33.         }
  34.     }
  35. }
  36.  
  37. namespace sub3{
  38.     bool check(){
  39.         return (n <= 300);
  40.     }
  41.  
  42.     ii calc(ii x , ii y){
  43.         if (x.fi > y.fi) return x;
  44.         if (y.fi > x.fi) return y;
  45.         ii ans = {x.fi , -1};
  46.         if (x.se != -1 && y.se != -1) ans.se = x.se + y.se;
  47.         return ans;
  48.     }
  49.  
  50.     void solve(){
  51.         ii ans = {0 , 0};
  52.         for (int i = 1 ; i <= n ; i++){
  53.             set<int> X , Y;
  54.             for (int j = i ; j <= n ; j++){
  55.                 if (L[i] != L[j]){
  56.                     if (sz(X) < 2) X.insert(R[j]);
  57.                 }
  58.                 if (R[i] != R[j]){
  59.                     if (sz(Y) < 2) Y.insert(L[j]);
  60.                 }
  61.                 if (sz(X) == 0) ans = calc(ans , {j - i + 1 , -1});
  62.                 if (sz(X) == 1) ans = calc(ans , {j - i + 1 , +1});
  63.                 if (sz(Y) == 0) ans = calc(ans , {j - i + 1 , -1});
  64.                 if (sz(Y) == 1) ans = calc(ans , {j - i + 1 , +1});
  65.             }
  66.         }
  67.         cout << ans.fi << " " << ans.se << "\n";
  68.     }
  69. }
  70.  
  71. namespace sub4{
  72.     #define lef(id) id * 2
  73.     #define rig(id) id * 2 + 1
  74.     struct segtree_min{
  75.         int st[4 * maxN];
  76.  
  77.         void init(){
  78.             for (int id = 1 ; id <= 4 * n ; id++) st[id] = +inf;
  79.         }
  80.  
  81.         void update(int id , int l , int r , int p , int x){
  82.             if (l == r){
  83.                 st[id] = x;
  84.                 return;
  85.             }
  86.             int mid = (l + r) / 2;
  87.             if (p <= mid){
  88.                 update(lef(id) , l , mid , p , x);
  89.             }
  90.             else{
  91.                 update(rig(id) , mid + 1 , r , p , x);
  92.             }
  93.             st[id] = min(st[lef(id)] , st[rig(id)]);
  94.         }
  95.  
  96.         int get(int id , int l , int r , int u , int v){
  97.             if (v < l || r < u) return +inf;
  98.             if (u <= l && r <= v) return st[id];
  99.             int mid = (l + r) / 2;
  100.             return min(get(lef(id) , l , mid , u , v) , get(rig(id) , mid + 1 , r , u , v));
  101.         }
  102.     } Min;
  103.  
  104.     struct segtree_max{
  105.         int st[4 * maxN];
  106.  
  107.         void init(){
  108.             for (int id = 1 ; id <= 4 * n ; id++) st[id] = -inf;
  109.         }
  110.  
  111.         void update(int id , int l , int r , int p , int x){
  112.             if (l == r){
  113.                 st[id] = x;
  114.                 return;
  115.             }
  116.             int mid = (l + r) / 2;
  117.             if (p <= mid){
  118.                 update(lef(id) , l , mid , p , x);
  119.             }
  120.             else{
  121.                 update(rig(id) , mid + 1 , r , p , x);
  122.             }
  123.             st[id] = max(st[lef(id)] , st[rig(id)]);
  124.         }
  125.  
  126.         int get(int id , int l , int r , int u , int v){
  127.             if (v < l || r < u) return -inf;
  128.             if (u <= l && r <= v) return st[id];
  129.             int mid = (l + r) / 2;
  130.             return max(get(lef(id) , l , mid , u , v) , get(rig(id) , mid + 1 , r , u , v));
  131.         }
  132.     } Max;
  133.  
  134.     ii calc(ii x , ii y){
  135.         if (x.fi > y.fi) return x;
  136.         if (y.fi > x.fi) return y;
  137.         ii ans = {x.fi , -1};
  138.         if (x.se != -1 && y.se != -1) ans.se = x.se + y.se;
  139.         return ans;
  140.     }
  141.  
  142.     ii ans = {0 , 0};
  143.  
  144.     void prepare(){
  145.         for (int i = 1 ; i <= sz(val) ; i++) event[i].clear();
  146.         Min.init(); Max.init();
  147.         for (int i = 1 ; i <= n ; i++){
  148.             Min.update(1 , 1 , n , i , R[i]);
  149.             Max.update(1 , 1 , n , i , R[i]);
  150.         }
  151.         for (int i = 1 ; i <= n ; i++){
  152.             event[L[i]].push_back(i);
  153.         }
  154.         for (int i = 1 ; i <= sz(val) ; i++){
  155.             for (int j : event[i]){
  156.                 Min.update(1 , 1 , n , j , +inf);
  157.                 Max.update(1 , 1 , n , j , -inf);
  158.             }
  159.             for (int j : event[i]){
  160.                 int lef = j , rig = n , pos = -1;
  161.                 while (lef <= rig){
  162.                     int mid = (lef + rig) / 2;
  163.                     int x = Min.get(1 , 1 , n , j , mid);
  164.                     int y = Max.get(1 , 1 , n , j , mid);
  165.                     if (x == +inf || x == y){
  166.                         pos = mid;
  167.                         lef = mid + 1;
  168.                     }
  169.                     else{
  170.                         rig = mid - 1;
  171.                     }
  172.                 }
  173.                 int x = Min.get(1 , 1 , n , j , pos);
  174.                 if (x == +inf){
  175.                     ans = calc(ans , {pos - j + 1 , -1});
  176.                 }
  177.                 else{
  178.                     ans = calc(ans , {pos - j + 1 , +1});
  179.                 }
  180.             }
  181.             for (int j : event[i]){
  182.                 Min.update(1 , 1 , n , j , R[j]);
  183.                 Max.update(1 , 1 , n , j , R[j]);
  184.             }
  185.         }
  186.     }
  187.  
  188.     void solve(){
  189.         prepare();
  190.         for (int i = 1 ; i <= n ; i++) swap(L[i] , R[i]);
  191.         prepare();
  192.         cout << ans.fi << " " << ans.se << "\n";
  193.     }
  194. }
  195.  
  196. void solve(){
  197.     cin >> n;
  198.     for (int i = 1 ; i <= n ; i++){
  199.         cin >> x[i] >> a[i] >> b[i];
  200.         L[i] = x[i] - a[i];
  201.         R[i] = x[i] + b[i];
  202.         val.push_back(L[i]);
  203.         val.push_back(R[i]);
  204.     }
  205.     unq(val);
  206.     for (int i = 1 ; i <= n ; i++){
  207.         L[i] = lower_bound(all(val) , L[i]) - val.begin() + 1;
  208.         R[i] = lower_bound(all(val) , R[i]) - val.begin() + 1;
  209.     }
  210.     if (sub1::check()) return sub1::solve();
  211.     if (sub3::check()) return sub3::solve();
  212.     return sub4::solve();
  213. }
  214.  
  215. #define name "ROADSIGNS"
  216.  
  217. int main(){
  218.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  219.     if (fopen(name".INP" , "r")){
  220.         freopen(name".INP" , "r" , stdin);
  221.         freopen(name".OUT" , "w" , stdout);
  222.     }
  223.     int t = 1; //cin >> t;
  224.     while (t--) solve();
  225.     return 0;
  226. }
  227.  
Success #stdin #stdout 0.01s 24116KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2 -2
https://ideone.com/aXiJwt
language:
C++ (gcc 8.3)
created:
8 days ago
visibility:
public

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!