oj.uz

Submission #974657

# Submission time Handle Problem Language Result Execution time Memory
974657 2024-05-03T15:22:12 Z Abito Strange Device (APIO19_strange_device) C++17
5 / 100
 3276 ms 524288 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
#define int long long
#define ll long long
typedef unsigned long long ull;
using namespace std;
const int N=1e6+5;
int n,a,b,l[N],r[N];
pair<int,int> f(int x){
    return {(x+x/b)%a,x%b};
}
map<pair<int,int>,int> mp;
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n>>a>>b;
    for (int i=1;i<=n;i++) cin>>l[i]>>r[i];
    vector<pair<int,int>> v;
    v.pb(f(0));mp[f(0)]=0;
    for (int i=1;;i++){
        if (mp.find(f(i))!=mp.end()) break;
        v.pb(f(i));
        mp[f(i)]=i;
    }int sz=v.size();//cout<<sz<<endl;
    vector<pair<int,int>> rng;
    for (int i=1;i<=n;i++){
        if (r[i]-l[i]+1>=sz) rng.pb({0,sz-1});
        int L=mp[f(l[i])],R=(L+r[i]-l[i]);
        if (R%sz>=L) rng.pb({L,R%sz});
        else{
            rng.pb({L,sz-1});
            rng.pb({0,R%sz});
        }
    }
    sort(rng.begin(),rng.end());
    set<pair<int,int>> s;
    pair<int,int> cur=rng[0];
    for (auto u:rng){
        int l=max(u.F,cur.F),r=min(u.S,cur.S);
        if (l>r){
            s.ep(cur);
            cur=u;
        }
        else{
            cur.F=min(cur.F,u.F);
            cur.S=max(cur.S,u.S);
        }
    }
    s.ep(cur);
    int ans=0;
    for (auto u:s) ans+=u.S-u.F+1;
    cout<<ans<<endl;
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2422 ms 510868 KB Output is correct
3 Correct 1845 ms 398224 KB Output is correct
4 Correct 4 ms 4056 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2508 KB Output is correct
7 Correct 2 ms 2964 KB Output is correct
8 Correct 2 ms 2652 KB Output is correct
9 Correct 4 ms 3544 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 31 ms 11804 KB Output is correct
16 Correct 49 ms 19124 KB Output is correct
17 Correct 727 ms 173392 KB Output is correct
18 Runtime error 3010 ms 524288 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Runtime error 3276 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 245 ms 77972 KB Output is correct
3 Correct 318 ms 78760 KB Output is correct
4 Correct 255 ms 67224 KB Output is correct
5 Correct 564 ms 138100 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 993 ms 211688 KB Output is correct
3 Runtime error 3066 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 993 ms 211688 KB Output is correct
3 Runtime error 3066 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 993 ms 211688 KB Output is correct
3 Runtime error 3066 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Runtime error 1412 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2422 ms 510868 KB Output is correct
3 Correct 1845 ms 398224 KB Output is correct
4 Correct 4 ms 4056 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2508 KB Output is correct
7 Correct 2 ms 2964 KB Output is correct
8 Correct 2 ms 2652 KB Output is correct
9 Correct 4 ms 3544 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 31 ms 11804 KB Output is correct
16 Correct 49 ms 19124 KB Output is correct
17 Correct 727 ms 173392 KB Output is correct
18 Runtime error 3010 ms 524288 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -