oj.uz

Submission #232443

# Submission time Handle Problem Language Result Execution time Memory
232443 2020-05-17T04:39:25 Z limabeans Strange Device (APIO19_strange_device) C++17
5 / 100
 609 ms 66780 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl




typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 1e6 + 5;



ll n, a, b;


ll getx(ll t) {
    return (t+t/b)%a;
}

ll gety(ll t) {
    return t%b;
}






ll merge(vector<pair<ll,ll>> v) {
    sort(v.begin(), v.end());
    // for (auto p: v) {
    // 	cout<<p.first<<" "<<p.second<<endl;
    // }
    
    ll res = 0;

    n = v.size();
    auto cur = v.front();
    for (int i=1; i<n; i++) {
	ll x=v[i].first;
	ll y=v[i].second;
	if (x>cur.second) {
	    res += cur.second-cur.first+1;
	    cur = v[i];
	} else {
	    cur.second=max(cur.second,y);
	}
    }
    res += cur.second-cur.first+1;
    return res;
}

vector<pair<ll,ll>> v;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>a>>b;

    v.resize(n);
    for (int i=0; i<n; i++) {
	cin>>v[i].first>>v[i].second;
    }

    if (a > 1e18/b) {
	//merge intervals
	ll res = merge(v);
	out(res);
    }



    vector<pair<ll,ll>> cv;
    
    for (int i=0; i<n; i++) {
	v[i].first %= (a*b);
	v[i].second %= (a*b);
	if (v[i].second>=v[i].first) {
	    cv.push_back(v[i]);
	} else {
	    cv.push_back({v[i].first,a*b-1});
	    cv.push_back({0,v[i].second});
	}
    }




    ll ans = merge(cv);
    out(ans);  

    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 384 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 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 391 ms 47572 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 536 ms 47572 KB Output is correct
3 Incorrect 542 ms 47516 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 536 ms 47572 KB Output is correct
3 Incorrect 542 ms 47516 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 536 ms 47572 KB Output is correct
3 Incorrect 542 ms 47516 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 67 ms 8940 KB Output is correct
3 Correct 59 ms 8940 KB Output is correct
4 Correct 609 ms 66780 KB Output is correct
5 Correct 63 ms 9068 KB Output is correct
6 Correct 67 ms 8812 KB Output is correct
7 Correct 60 ms 8812 KB Output is correct
8 Correct 64 ms 8816 KB Output is correct
9 Correct 62 ms 8940 KB Output is correct
10 Correct 62 ms 8812 KB Output is correct
11 Correct 60 ms 8940 KB Output is correct
12 Correct 56 ms 8812 KB Output is correct
13 Correct 62 ms 8812 KB Output is correct
14 Correct 586 ms 66772 KB Output is correct
15 Incorrect 67 ms 8812 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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