oj.uz

Submission #252121

# Submission time Handle Problem Language Result Execution time Memory
252121 2020-07-24T09:15:19 Z khangal Strange Device (APIO19_strange_device) C++14
20 / 100
 2494 ms 181528 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef double db;
typedef vector<long long> vl;
typedef pair<long long , long long > pl;
const int N=1e6+1;
#define po pop_back
#define pb push_back
#define mk make_pair
#define lw lower_bound
#define up upper_bound
#define ff first
#define ss second
#define boost ios_base::sync_with_stdio(); cin.tie(0); cout.tie(0);
#define MOD 1000000007
#define MAX 1e18 
#define MIN -1e18
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define per(i,a,b) for(ll i=b;i>=a;i--)
#define con continue
#define freopen freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define PI 3.14159265358979323846264338327950288419716939937510582097494459230781640628
// typedef tree<ll , null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
// template< typename T>
// using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll n,m,ans,mid,mn,mx,cnt,T,sum,h1,h2,e[1234567],b[1234567],c[1234567],d[1<<20],k,i,j,l,x,y,r,z,h,a[1234567],w,c1[1234][1234];
bool used[1234567],used1[1234567];
pl p[1234567];
string s,s1[1234567];
map<ll,ll> mp;
map<pl,ll> mpl;
vector<pl> vec,vec1,ansvec;
vector<ll> v[1234567],v1[1234567];
vector<ll> vp[1234567];
set<pl> st;
set<ll> stl,str;
stack <ll> sta;
int main(){
    ll A,B;
    cin>>n>>A>>B;
    ll L[1234567],R[1234567];
    rep(i,1,n){
        cin>>L[i]>>R[i];
        x+=R[i]-L[i]+1;
    }
    if(x<=1e6){
        rep(i,1,n){
            rep(j,L[i],R[i]){
                x = (j+j/B)%A;
                y = j%B;
                st.insert({x,y});
            }
        }
        cout<<st.size();
        return 0;
    }
    ll t = A*B;
    rep(i,1,n){
        l=L[i];
        r=R[i];
        if(r - l + 1 >= t)
            return cout << t , 0;
        l %= t, r %= t;
        if(l > r){
            vec.pb({l , -1});
            vec.pb({t , 1});
            vec.pb({0 , -1});
            vec.pb({r + 1 , 1});
        }
        else{
            vec.pb({l, -1});
            vec.pb({r + 1, 1});
        }
    }
    sort(vec.begin() , vec.end());
    for(auto i : vec){
        if(i.ss == 1) {
            if(sta.size() == 1)
                ans += i.ff - sta.top();
            sta.pop();
        }
        else
            sta.push(i.ff);
    }
    cout<<ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 125944 KB Output is correct
2 Correct 137 ms 138208 KB Output is correct
3 Correct 163 ms 143736 KB Output is correct
4 Correct 66 ms 126584 KB Output is correct
5 Correct 65 ms 126072 KB Output is correct
6 Correct 75 ms 126072 KB Output is correct
7 Correct 66 ms 126208 KB Output is correct
8 Correct 65 ms 126072 KB Output is correct
9 Correct 75 ms 126840 KB Output is correct
10 Correct 79 ms 125944 KB Output is correct
11 Correct 61 ms 125944 KB Output is correct
12 Correct 70 ms 125944 KB Output is correct
13 Correct 68 ms 125944 KB Output is correct
14 Correct 79 ms 125944 KB Output is correct
15 Correct 108 ms 132728 KB Output is correct
16 Correct 120 ms 132624 KB Output is correct
17 Correct 310 ms 133880 KB Output is correct
18 Correct 70 ms 125944 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 125944 KB Output is correct
2 Correct 73 ms 126072 KB Output is correct
3 Correct 66 ms 125944 KB Output is correct
4 Correct 81 ms 125944 KB Output is correct
5 Correct 80 ms 125944 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 126072 KB Output is correct
2 Correct 219 ms 158072 KB Output is correct
3 Correct 250 ms 157892 KB Output is correct
4 Correct 211 ms 156408 KB Output is correct
5 Correct 1652 ms 181528 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 125944 KB Output is correct
2 Correct 2343 ms 174744 KB Output is correct
3 Incorrect 2290 ms 175044 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 125944 KB Output is correct
2 Correct 2343 ms 174744 KB Output is correct
3 Incorrect 2290 ms 175044 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 125944 KB Output is correct
2 Correct 2343 ms 174744 KB Output is correct
3 Incorrect 2290 ms 175044 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 126000 KB Output is correct
2 Correct 310 ms 131816 KB Output is correct
3 Correct 296 ms 131816 KB Output is correct
4 Correct 2494 ms 174824 KB Output is correct
5 Correct 302 ms 131868 KB Output is correct
6 Correct 299 ms 131816 KB Output is correct
7 Correct 303 ms 131816 KB Output is correct
8 Correct 300 ms 131744 KB Output is correct
9 Correct 287 ms 131816 KB Output is correct
10 Correct 295 ms 131816 KB Output is correct
11 Correct 296 ms 131816 KB Output is correct
12 Correct 302 ms 131816 KB Output is correct
13 Correct 302 ms 131816 KB Output is correct
14 Correct 2432 ms 174640 KB Output is correct
15 Incorrect 306 ms 131816 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 125944 KB Output is correct
2 Correct 137 ms 138208 KB Output is correct
3 Correct 163 ms 143736 KB Output is correct
4 Correct 66 ms 126584 KB Output is correct
5 Correct 65 ms 126072 KB Output is correct
6 Correct 75 ms 126072 KB Output is correct
7 Correct 66 ms 126208 KB Output is correct
8 Correct 65 ms 126072 KB Output is correct
9 Correct 75 ms 126840 KB Output is correct
10 Correct 79 ms 125944 KB Output is correct
11 Correct 61 ms 125944 KB Output is correct
12 Correct 70 ms 125944 KB Output is correct
13 Correct 68 ms 125944 KB Output is correct
14 Correct 79 ms 125944 KB Output is correct
15 Correct 108 ms 132728 KB Output is correct
16 Correct 120 ms 132624 KB Output is correct
17 Correct 310 ms 133880 KB Output is correct
18 Correct 70 ms 125944 KB Output is correct
19 Correct 66 ms 125944 KB Output is correct
20 Correct 73 ms 126072 KB Output is correct
21 Correct 66 ms 125944 KB Output is correct
22 Correct 81 ms 125944 KB Output is correct
23 Correct 80 ms 125944 KB Output is correct
24 Correct 67 ms 126072 KB Output is correct
25 Correct 219 ms 158072 KB Output is correct
26 Correct 250 ms 157892 KB Output is correct
27 Correct 211 ms 156408 KB Output is correct
28 Correct 1652 ms 181528 KB Output is correct
29 Correct 67 ms 125944 KB Output is correct
30 Correct 2343 ms 174744 KB Output is correct
31 Incorrect 2290 ms 175044 KB Output isn't correct
32 Halted 0 ms 0 KB -