Submission #708177

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
708177	2023-03-11T08:53:34 Z	veehj	Strange Device (APIO19_strange_device)	C++17	35 / 100	1743 ms	69088 KB

strange_device

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(x) (x).begin(), (x).end()
ll gcd(ll a, ll b){ return b ? gcd(b,a%b) : a; }

int main() {
  ll n, a, b; cin >> n >> a >> b;
  a/=gcd(a, b+1);
  __int128_t ml = a*b;
  map<ll, ll> mp;
  while(n--){
    ll l, r; cin >> l >> r;
    if(r-l+1>=ml){
      cout << (ll)ml << endl;
      return 0;
    }
    l%=ml;
    r%=ml; 
    if(l>r){
      mp[l]++;
      mp[ml]--;
      mp[0]++;
      mp[r+1]--;
    }
    else{
      mp[l]++;
      mp[r+1]--;
    }
  }
  // 1 0 1 -1 -1 0 1 0 -1
  // 1 1 2  1  0 0 1 1  0
  ll cnt=0, nw=0, ans=0, pcnt=0;
  for(auto& u : mp){
    cnt+=u.S;
    // cout << "[" << u.first << ',' << u.second << ']' << cnt << endl;
    if(!pcnt) nw=u.F;
    if(!cnt) ans+=u.F-nw;
    pcnt=cnt;
  }
  cout << ans;
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	16 ms	1248 KB	Output is correct
3	Correct	18 ms	1256 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	300 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	296 KB	Output is correct
16	Correct	19 ms	1204 KB	Output is correct
17	Correct	171 ms	7764 KB	Output is correct
18	Incorrect	1 ms	212 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Incorrect	0 ms	212 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	304 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	2 ms	372 KB	Output is correct
4	Correct	2 ms	312 KB	Output is correct
5	Correct	899 ms	472 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1594 ms	65284 KB	Output is correct
3	Correct	1695 ms	63560 KB	Output is correct
4	Correct	1645 ms	69088 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1594 ms	65284 KB	Output is correct
3	Correct	1695 ms	63560 KB	Output is correct
4	Correct	1645 ms	69088 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1643 ms	68916 KB	Output is correct
7	Correct	1601 ms	69068 KB	Output is correct
8	Correct	1659 ms	69032 KB	Output is correct
9	Correct	1743 ms	68900 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1594 ms	65284 KB	Output is correct
3	Correct	1695 ms	63560 KB	Output is correct
4	Correct	1645 ms	69088 KB	Output is correct
5	Correct	1 ms	300 KB	Output is correct
6	Correct	150 ms	10252 KB	Output is correct
7	Correct	152 ms	10252 KB	Output is correct
8	Correct	162 ms	10172 KB	Output is correct
9	Correct	156 ms	10268 KB	Output is correct
10	Correct	147 ms	10288 KB	Output is correct
11	Correct	163 ms	10224 KB	Output is correct
12	Correct	159 ms	10224 KB	Output is correct
13	Correct	163 ms	10316 KB	Output is correct
14	Correct	148 ms	10196 KB	Output is correct
15	Correct	176 ms	10236 KB	Output is correct
16	Correct	166 ms	10184 KB	Output is correct
17	Correct	156 ms	10136 KB	Output is correct
18	Correct	1600 ms	68980 KB	Output is correct
19	Correct	1615 ms	68984 KB	Output is correct
20	Correct	1716 ms	69000 KB	Output is correct
21	Correct	158 ms	10196 KB	Output is correct
22	Correct	155 ms	10260 KB	Output is correct
23	Correct	425 ms	12876 KB	Output is correct

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	180 ms	8008 KB	Output is correct
3	Correct	162 ms	7928 KB	Output is correct
4	Correct	1658 ms	63576 KB	Output is correct
5	Correct	168 ms	8128 KB	Output is correct
6	Correct	185 ms	8120 KB	Output is correct
7	Correct	168 ms	8028 KB	Output is correct
8	Correct	177 ms	8120 KB	Output is correct
9	Correct	170 ms	8096 KB	Output is correct
10	Correct	157 ms	8100 KB	Output is correct
11	Correct	165 ms	8228 KB	Output is correct
12	Correct	162 ms	8180 KB	Output is correct
13	Correct	168 ms	8148 KB	Output is correct
14	Correct	1686 ms	63336 KB	Output is correct
15	Correct	162 ms	7948 KB	Output is correct
16	Correct	1530 ms	69032 KB	Output is correct
17	Correct	1508 ms	69036 KB	Output is correct
18	Incorrect	1 ms	300 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	16 ms	1248 KB	Output is correct
3	Correct	18 ms	1256 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	300 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	296 KB	Output is correct
16	Correct	19 ms	1204 KB	Output is correct
17	Correct	171 ms	7764 KB	Output is correct
18	Incorrect	1 ms	212 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Submission #708177

Compilation message