oj.uz

답안 #232445

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
232445 2020-05-17T04:44:28 Z limabeans 이상한 기계 (APIO19_strange_device) C++17
5 / 100
 595 ms 47572 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 {
	    
	    assert(v[i].first>v[i].second);
	    
	    cv.push_back({v[i].first,a*b});
	    cv.push_back({1,v[i].second});
	}
    }




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

    return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 9 ms 1024 KB Output is correct
3 Correct 10 ms 896 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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 4 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 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 396 ms 47544 KB Output is correct

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 530 ms 47556 KB Output is correct
3 Incorrect 544 ms 47572 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 530 ms 47556 KB Output is correct
3 Incorrect 544 ms 47572 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 530 ms 47556 KB Output is correct
3 Incorrect 544 ms 47572 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 59 ms 5184 KB Output is correct
3 Correct 62 ms 5228 KB Output is correct
4 Correct 595 ms 47444 KB Output is correct
5 Correct 58 ms 5228 KB Output is correct
6 Correct 58 ms 5100 KB Output is correct
7 Correct 59 ms 5228 KB Output is correct
8 Correct 60 ms 5228 KB Output is correct
9 Correct 60 ms 5228 KB Output is correct
10 Correct 59 ms 5100 KB Output is correct
11 Correct 59 ms 5100 KB Output is correct
12 Correct 55 ms 5232 KB Output is correct
13 Correct 61 ms 5228 KB Output is correct
14 Correct 579 ms 47456 KB Output is correct
15 Incorrect 62 ms 5100 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 9 ms 1024 KB Output is correct
3 Correct 10 ms 896 KB Output is correct
4 Incorrect 5 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -