oj.uz

Submission #625700

# Submission time Handle Problem Language Result Execution time Memory
625700 2022-08-10T17:19:48 Z slime Strange Device (APIO19_strange_device) C++17
65 / 100
 840 ms 76088 KB 
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 3e5 + 10;
const int MOD = 1e9 + 7;
#define ll __int128
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
ll read() { int x; cin >> x; return (ll)x; }
long long bm(long long b, long long p) {
  if(p==0) return 1 % MOD;
  long long r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
long long inv(long long b) { 
  return bm(b, MOD-2);
}
long long f[MAXN];
long long nCr(int n, int r) { 
  long long ans = f[n]; ans *= inv(f[r]); ans %= MOD;
  ans *= inv(f[n-r]); ans %= MOD; return ans;
}
long long fib[MAXN], lucas[MAXN];
void precomp() { 
  for(int i=0; i<MAXN; i++) f[i] = (i == 0 ? 1 % MOD : (f[i-1] * i) % MOD); 
  lucas[0] = 2;
  lucas[1] = 1;
  for(int i=2; i<MAXN; i++) lucas[i] = (lucas[i-2] + lucas[i-1]) % MOD;
  fib[0] = 0;
  fib[1] = 1;
  for(int i=2; i<MAXN; i++) fib[i] = (fib[i-2] + fib[i-1]) % MOD;
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void gay(int i) { cout << "Case #" << i << ": "; }
int csb(int l, int r, int k) { // count number of [l, r] such that i & 2^k > 0
  if(l > r) return 0;
  if(l == 0) {
    int s = r / (1ll << (k+1)); // number of complete cycles
    int t = r % (1ll << (k+1));
    int ans = s * (1ll << k);
    ans += (t >= (1ll << k) ? t - (1ll << k) + 1 : 0);
    return ans;
  }
  else return csb(0, r, k) - csb(0, l - 1, k);
}
int lis(vector<int> a) {
  int n = a.size();
  int bucket[n+1];
  for(int i=1; i<=n; i++) bucket[i] = 1e18;
  int ans = 1;
  for(int x: a) {
    auto it = lower_bound(bucket + 1, bucket +n +1, x);
    int d = distance(bucket, it);
    ans = max(ans, d);
    bucket[d] = min(bucket[d], x);
  }
  return ans;
}
bool cmp(pair<int, char> a, pair<int, char> b) {
  if(a.first != b.first) return a.first < b.first;
  return a.second > b.second;
}
void solve(int tc) {
  int N;
  cin >> N;
  int A, B;
  cin >> A >> B;
  int g = gcd(A, B + 1);
  int len = A / g;
  set<int > st;
  vector<pair<int, char> > segments;
  for(int i=0; i<N; i++) {
    int L, R;
    cin >> L >> R;
    if(L % (B * len) > R % (B * len)) {
      segments.emplace_back(L % (B * len), 'S');
      segments.emplace_back(B * len - 1, 'E');
      segments.emplace_back(0, 'S');
      segments.emplace_back(R % (B * len), 'E');
    }
    else {
      segments.emplace_back(L % (B * len), 'S');
      segments.emplace_back(R % (B * len), 'E');
    }
  }
  sort(segments.begin(), segments.end(), cmp);
  int ans = 0;
  int str = -1;
  int bal = 0;
  for(pair<int, char> x: segments) {
    if(x.second == 'S') {
      bal++;
      if(bal == 1) str = x.first;
    }
    else {
      bal--;
      if(bal == 0) ans += x.first - str + 1;
    }
  }
  cout << ans << "\n";
} 
int32_t main() {
  precomp();
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
// I don't know geometry.
// Teaming is unfair.

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7252 KB Output is correct
2 Correct 14 ms 8280 KB Output is correct
3 Correct 13 ms 8396 KB Output is correct
4 Correct 8 ms 7304 KB Output is correct
5 Correct 9 ms 7328 KB Output is correct
6 Correct 8 ms 7336 KB Output is correct
7 Correct 7 ms 7368 KB Output is correct
8 Correct 8 ms 7380 KB Output is correct
9 Correct 8 ms 7368 KB Output is correct
10 Correct 8 ms 7252 KB Output is correct
11 Correct 10 ms 7288 KB Output is correct
12 Correct 8 ms 7372 KB Output is correct
13 Correct 8 ms 7252 KB Output is correct
14 Correct 8 ms 7252 KB Output is correct
15 Correct 9 ms 7380 KB Output is correct
16 Correct 14 ms 8408 KB Output is correct
17 Correct 86 ms 14256 KB Output is correct
18 Correct 8 ms 7252 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7372 KB Output is correct
2 Incorrect 10 ms 7256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7324 KB Output is correct
2 Correct 10 ms 7384 KB Output is correct
3 Correct 10 ms 7424 KB Output is correct
4 Correct 9 ms 7432 KB Output is correct
5 Correct 386 ms 63928 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7252 KB Output is correct
2 Correct 657 ms 58572 KB Output is correct
3 Correct 713 ms 75968 KB Output is correct
4 Correct 688 ms 75988 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7252 KB Output is correct
2 Correct 657 ms 58572 KB Output is correct
3 Correct 713 ms 75968 KB Output is correct
4 Correct 688 ms 75988 KB Output is correct
5 Correct 8 ms 7380 KB Output is correct
6 Correct 664 ms 75948 KB Output is correct
7 Correct 647 ms 75916 KB Output is correct
8 Correct 662 ms 76020 KB Output is correct
9 Correct 807 ms 75924 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7252 KB Output is correct
2 Correct 657 ms 58572 KB Output is correct
3 Correct 713 ms 75968 KB Output is correct
4 Correct 688 ms 75988 KB Output is correct
5 Correct 7 ms 7252 KB Output is correct
6 Correct 63 ms 14276 KB Output is correct
7 Correct 69 ms 14300 KB Output is correct
8 Correct 63 ms 14256 KB Output is correct
9 Correct 64 ms 14340 KB Output is correct
10 Correct 82 ms 14348 KB Output is correct
11 Correct 68 ms 14308 KB Output is correct
12 Correct 62 ms 14304 KB Output is correct
13 Correct 77 ms 14340 KB Output is correct
14 Correct 64 ms 14332 KB Output is correct
15 Correct 85 ms 14280 KB Output is correct
16 Correct 77 ms 14300 KB Output is correct
17 Correct 74 ms 14312 KB Output is correct
18 Correct 698 ms 76088 KB Output is correct
19 Correct 630 ms 75900 KB Output is correct
20 Correct 834 ms 75904 KB Output is correct
21 Correct 82 ms 14340 KB Output is correct
22 Correct 59 ms 14320 KB Output is correct
23 Correct 154 ms 33708 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7252 KB Output is correct
2 Correct 75 ms 14276 KB Output is correct
3 Correct 80 ms 14352 KB Output is correct
4 Correct 840 ms 75960 KB Output is correct
5 Correct 74 ms 14276 KB Output is correct
6 Correct 72 ms 14360 KB Output is correct
7 Correct 76 ms 14364 KB Output is correct
8 Correct 78 ms 14272 KB Output is correct
9 Correct 72 ms 14304 KB Output is correct
10 Correct 81 ms 14344 KB Output is correct
11 Correct 74 ms 14356 KB Output is correct
12 Correct 69 ms 14232 KB Output is correct
13 Correct 85 ms 14300 KB Output is correct
14 Correct 818 ms 75988 KB Output is correct
15 Correct 84 ms 14280 KB Output is correct
16 Correct 618 ms 75916 KB Output is correct
17 Correct 680 ms 76016 KB Output is correct
18 Correct 7 ms 7252 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7252 KB Output is correct
2 Correct 14 ms 8280 KB Output is correct
3 Correct 13 ms 8396 KB Output is correct
4 Correct 8 ms 7304 KB Output is correct
5 Correct 9 ms 7328 KB Output is correct
6 Correct 8 ms 7336 KB Output is correct
7 Correct 7 ms 7368 KB Output is correct
8 Correct 8 ms 7380 KB Output is correct
9 Correct 8 ms 7368 KB Output is correct
10 Correct 8 ms 7252 KB Output is correct
11 Correct 10 ms 7288 KB Output is correct
12 Correct 8 ms 7372 KB Output is correct
13 Correct 8 ms 7252 KB Output is correct
14 Correct 8 ms 7252 KB Output is correct
15 Correct 9 ms 7380 KB Output is correct
16 Correct 14 ms 8408 KB Output is correct
17 Correct 86 ms 14256 KB Output is correct
18 Correct 8 ms 7252 KB Output is correct
19 Correct 8 ms 7372 KB Output is correct
20 Incorrect 10 ms 7256 KB Output isn't correct
21 Halted 0 ms 0 KB -