Submission #1059852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059852		dpsaveslives	Strange Device (APIO19_strange_device)	C++17	100 / 100	1174 ms	101956 KiB

strange_device

#include <bits/stdc++.h>
#define int long long
using namespace std;

ostream& operator<<(ostream& out, __int128_t x){
	string s; while(x) s.push_back(x % 10 + '0'), x /= 10;
	reverse(s.begin(), s.end()); return out << s;
}

int32_t main(){
    int N,A,B; cin >> N >> A >> B;
    __int128_t C = (__int128_t)B*(A/__gcd(A,B+1));
  	vector<pair<__int128_t, __int128_t>> ranges;
  	for(int i = 0;i<N;++i){
        int l,r; cin >> l >> r;
        if(r-l+1 >= C){
            cout << C << "\n";
            return 0;
        }
        if(l/C == r/C){
            ranges.push_back({l%C,1});
            ranges.push_back({r%C + 1,-1});
        }
        else{
            ranges.push_back({l%C,1});
            ranges.push_back({0,1});
            ranges.push_back({r%C+1,-1});
        }
  	}
	ranges.push_back({C, 0});
	sort(ranges.begin(),ranges.end());
	int cnt = 0, ans = 0;
	for(int i = 0;i<ranges.size()-1;++i){
        cnt += ranges[i].second;
        if(cnt > 0){
            ans += ranges[i+1].first-ranges[i].first;
        }
	}
	cout << ans << "\n";
	return 0;
}

Compilation message (stderr)

strange_device.cpp: In function 'int32_t main()':
strange_device.cpp:33:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<__int128, __int128> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for(int i = 0;i<ranges.size()-1;++i){
      |                ~^~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 30 / 30