Submission #708168

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
708168	2023-03-11T07:54:18 Z	veehj	Strange Device (APIO19_strange_device)	C++17	35 / 100	1787 ms	100216 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){if(!b)return a;else return gcd(b,a%b);}

int main() {
  ll n, a, b; cin >> n >> a >> b;
  a/=gcd(a, b+1);
  map<ll, ll> mp;
  while(n--){
    ll l, r; cin >> l >> r;
    if(r-l+1>=a*b){
      cout << a*b << endl;
      return 0;
    }
    l%=a*b;
    r%=a*b; 
    if(l>r){
      mp[l]++;
      mp[a*b]--;
      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	0 ms	212 KB	Output is correct
2	Correct	16 ms	924 KB	Output is correct
3	Correct	17 ms	852 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 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	1 ms	304 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	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	15 ms	1204 KB	Output is correct
17	Correct	160 ms	10280 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	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Incorrect	1 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	212 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	2 ms	368 KB	Output is correct
4	Correct	2 ms	340 KB	Output is correct
5	Correct	896 ms	272 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	1587 ms	63008 KB	Output is correct
3	Correct	1647 ms	62880 KB	Output is correct
4	Correct	1735 ms	100040 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	1587 ms	63008 KB	Output is correct
3	Correct	1647 ms	62880 KB	Output is correct
4	Correct	1735 ms	100040 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1613 ms	100052 KB	Output is correct
7	Correct	1601 ms	100004 KB	Output is correct
8	Correct	1709 ms	100016 KB	Output is correct
9	Correct	1787 ms	100216 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	1587 ms	63008 KB	Output is correct
3	Correct	1647 ms	62880 KB	Output is correct
4	Correct	1735 ms	100040 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	166 ms	10232 KB	Output is correct
7	Correct	151 ms	10212 KB	Output is correct
8	Correct	149 ms	10260 KB	Output is correct
9	Correct	154 ms	10184 KB	Output is correct
10	Correct	155 ms	10228 KB	Output is correct
11	Correct	144 ms	10176 KB	Output is correct
12	Correct	160 ms	10232 KB	Output is correct
13	Correct	169 ms	10276 KB	Output is correct
14	Correct	151 ms	10292 KB	Output is correct
15	Correct	163 ms	10176 KB	Output is correct
16	Correct	209 ms	10188 KB	Output is correct
17	Correct	158 ms	10276 KB	Output is correct
18	Correct	1617 ms	100084 KB	Output is correct
19	Correct	1774 ms	100052 KB	Output is correct
20	Correct	1724 ms	100104 KB	Output is correct
21	Correct	147 ms	10228 KB	Output is correct
22	Correct	156 ms	10268 KB	Output is correct
23	Correct	423 ms	12812 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	167 ms	6804 KB	Output is correct
3	Correct	159 ms	6748 KB	Output is correct
4	Correct	1562 ms	63064 KB	Output is correct
5	Correct	164 ms	6796 KB	Output is correct
6	Correct	186 ms	6732 KB	Output is correct
7	Correct	163 ms	6732 KB	Output is correct
8	Correct	168 ms	6816 KB	Output is correct
9	Correct	156 ms	6760 KB	Output is correct
10	Correct	157 ms	6888 KB	Output is correct
11	Correct	166 ms	6732 KB	Output is correct
12	Correct	148 ms	6836 KB	Output is correct
13	Correct	159 ms	6936 KB	Output is correct
14	Correct	1743 ms	63016 KB	Output is correct
15	Correct	156 ms	6608 KB	Output is correct
16	Correct	1618 ms	100132 KB	Output is correct
17	Correct	1570 ms	100172 KB	Output is correct
18	Incorrect	1 ms	212 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	16 ms	924 KB	Output is correct
3	Correct	17 ms	852 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 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	1 ms	304 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	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	15 ms	1204 KB	Output is correct
17	Correct	160 ms	10280 KB	Output is correct
18	Incorrect	1 ms	212 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Submission #708168

Compilation message