oj.uz

답안 #932774

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
932774 2024-02-24T07:41:44 Z 12345678 이상한 기계 (APIO19_strange_device) C++17
10 / 100
 727 ms 116076 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e6+5;
ll n, a, b, l[nx], r[nx], sm, p, mx, res;
set<pair<ll, ll>> s;

void add_range(ll x, ll y)
{
    x=x%p;
    y=y%p;
    if (y<x) y+=p;
    s.insert({x, min(p-1, y)});
    if (y>=p) s.insert({0, y-p});
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>a>>b;
    p=a*b;
    for (int i=1; i<=n; i++) cin>>l[i]>>r[i], mx=max(mx, r[i]-l[i]+1), sm+=(r[i]-l[i]+1);
    if (a>=(LLONG_MAX-1)/b+1) return cout<<sm, 0;
    if (mx>=p) return cout<<p, 0;
    for (int i=1; i<=n; i++) add_range(l[i], r[i]);
    //for (auto [x, y]:s) cout<<"val "<<x<<' '<<y<<'\n';
    for (auto itr=s.begin(); itr!=s.end()&&next(itr)!=s.end();)
    {
        auto itr2=next(itr);
        pair<ll, ll> nw;
        if (itr2->first>itr->second+1) itr=itr2;
        else nw={itr->first, max(itr->second, itr2->second)}, s.erase(itr), s.erase(itr2), s.insert(nw), itr=s.find(nw);
    }
    for (auto [x, y]:s) res+=y-x+1;
    cout<<res;
}

Subtask #1
0 / 10.0

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

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2512 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2528 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 190 ms 41044 KB Output is correct

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 55 ms 16620 KB Output is correct
3 Correct 55 ms 16724 KB Output is correct
4 Correct 633 ms 116076 KB Output is correct
5 Correct 55 ms 16748 KB Output is correct
6 Correct 59 ms 16724 KB Output is correct
7 Correct 54 ms 16732 KB Output is correct
8 Correct 55 ms 16720 KB Output is correct
9 Correct 56 ms 16712 KB Output is correct
10 Correct 49 ms 16736 KB Output is correct
11 Correct 51 ms 16580 KB Output is correct
12 Correct 50 ms 16736 KB Output is correct
13 Correct 63 ms 16740 KB Output is correct
14 Correct 727 ms 115796 KB Output is correct
15 Incorrect 58 ms 16712 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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