fork download
copy 
  1. // ~~ icebear love attttttt ~~
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define int long long
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7. typedef pair<int, ii> iii;
  8.  
  9. template<class T>
  10.     bool minimize(T &a, const T &b) {
  11.         if (a > b) return a = b, true;
  12.         return false;
  13.     }
  14.  
  15. template<class T>
  16.     bool maximize(T &a, const T &b) {
  17.         if (a < b) return a = b, true;
  18.         return false;
  19.     }
  20.  
  21. #define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
  22. #define FORR(i,a,b) for(int i=(a); i>=(b); --i)
  23. #define REP(i, n) for(int i=0; i<(n); ++i)
  24. #define RED(i, n) for(int i=(n)-1; i>=0; --i)
  25. #define MASK(i) (1LL << (i))
  26. #define mp make_pair
  27. #define pb push_back
  28. #define fi first
  29. #define se second
  30. #define all(x) x.begin(), x.end()
  31. #define task "roadsigns"
  32.  
  33. const int MOD = 1e9 + 7;
  34. const int inf = 1e9 + 27092008;
  35. const ll INF = 1e18 + 27092008;
  36. const int N = 4e5 + 5;
  37. int n, x[N], a[N], b[N];
  38. int A[N], B[N];
  39.  
  40. void init(void) {
  41.     cin >> n;
  42.     FOR(i, 1, n) {
  43.         cin >> x[i] >> a[i] >> b[i];
  44.         A[i] = x[i] - a[i];
  45.         B[i] = x[i] + b[i];
  46.     }
  47. }
  48.  
  49. namespace Subtask1 {
  50.     bool check() {
  51.         FOR(i, 1, n) if (a[i] != a[1] || b[i] != b[1])
  52.             return false;
  53.         return true;
  54.     }
  55.  
  56.     void solve() {
  57.         cout << 2 << ' ' << 2 * (n - 1);
  58.     }
  59. }
  60.  
  61. namespace Subtask2 {
  62.     int range[N]; // first j > i that A[j] != A[i]
  63.     bool check() {
  64.         FOR(i, 1, n) if (a[i] != a[1])
  65.             return false;
  66.         return true;
  67.     }
  68.  
  69.     void solve() {
  70.         FORR(i, n, 1) range[i] = (A[i] != A[i + 1] ? i + 1 : range[i + 1]);
  71.         int maxLen = 0, numLen = 0;
  72.         FOR(u, 1, n - 1) {
  73.             // L = A[u]
  74.             int j = range[u];
  75.             int v = j + 1;
  76.             if (A[v] == A[u]) v = range[v];
  77.             if (maximize(maxLen, v - u)) numLen = 1;
  78.             else if (maxLen == v - u) numLen++;
  79.  
  80.             // R = B[u]
  81.             v = range[u + 1];
  82.             if (maximize(maxLen, v - u)) numLen = 1;
  83.             else if (maxLen == v - u) numLen++;
  84.         }
  85.         cout << maxLen << ' ' << numLen;
  86.     }
  87. }
  88.  
  89. namespace Subtask34 {
  90.     bool check() {
  91.         return n <= 10000;
  92.     }
  93.  
  94.     int rangeA[N], rangeB[N];
  95.     void solve() {
  96.         FORR(i, n, 1) rangeA[i] = (A[i] != A[i + 1] ? i + 1 : rangeA[i + 1]);
  97.         FORR(i, n, 1) rangeB[i] = (B[i] != B[i + 1] ? i + 1 : rangeB[i + 1]);
  98.         if (max(rangeA[1], rangeB[1]) == n + 1) {
  99.             cout << n << ' ' << -1;
  100.             return;
  101.         }
  102.         int maxLen = 0, numLen = 0;
  103.         FOR(u, 1, n) {
  104.             // L = A[u]
  105.             int j = rangeA[u];
  106.             int v = j;
  107.             while(v <= n && (A[v] == A[u] || B[v] == B[j])) v++;
  108.             if (maximize(maxLen, v - u)) numLen = 1;
  109.             else if (maxLen == v - u) numLen++;
  110.  
  111.             // R = B[u]
  112.             j = rangeB[u];
  113.             v = j;
  114.             while(v <= n && (B[v] == B[u] || A[v] == A[j])) v++;
  115.             if (maximize(maxLen, v - u)) numLen = 1;
  116.             else if (maxLen == v - u) numLen++;
  117.         }
  118.  
  119.         cout << maxLen << ' ' << numLen;
  120.     }
  121. }
  122.  
  123. void process(void) {
  124.     if (Subtask1 :: check()) Subtask1 :: solve();
  125.     else if (Subtask2 :: check()) Subtask2 :: solve();
  126.     else if (Subtask34 :: check()) Subtask34 :: solve();
  127. }
  128.  
  129. signed main() {
  130.     ios_base::sync_with_stdio(0);
  131.     cin.tie(0); cout.tie(0);
  132.     if (fopen(task".inp", "r")) {
  133.         freopen(task".inp", "r", stdin);
  134.         freopen(task".out", "w", stdout);
  135.     }
  136.     int tc = 1;
  137. //    cin >> tc;
  138.     while(tc--) {
  139.         init();
  140.         process();
  141.     }
  142.     return 0;
  143. }
  144.  
Success #stdin #stdout 0.01s 5268KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2 -2
https://ideone.com/YW6SPe
language:
C++ (gcc 8.3)
created:
7 hours 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!