Submission #252134

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
252134	2020-07-24T09:47:42 Z	khangal	Strange Device (APIO19_strange_device)	C++14	35 / 100	2463 ms	181380 KB

strange_device

#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];
    ll t = A/__gcd(A,(B+1))*B;
    rep(i,1,n)cin>>L[i]>>R[i];
    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
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	69 ms	126032 KB	Output is correct
2	Correct	90 ms	126740 KB	Output is correct
3	Correct	92 ms	126836 KB	Output is correct
4	Correct	68 ms	125964 KB	Output is correct
5	Correct	67 ms	125944 KB	Output is correct
6	Correct	69 ms	125944 KB	Output is correct
7	Correct	74 ms	125944 KB	Output is correct
8	Correct	78 ms	126072 KB	Output is correct
9	Correct	67 ms	125944 KB	Output is correct
10	Correct	74 ms	125944 KB	Output is correct
11	Correct	75 ms	125944 KB	Output is correct
12	Correct	72 ms	125948 KB	Output is correct
13	Correct	73 ms	125944 KB	Output is correct
14	Correct	68 ms	125944 KB	Output is correct
15	Correct	78 ms	125944 KB	Output is correct
16	Correct	97 ms	126836 KB	Output is correct
17	Correct	305 ms	131820 KB	Output is correct
18	Incorrect	67 ms	125944 KB	Output isn't correct

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	73 ms	125944 KB	Output is correct
2	Correct	80 ms	126072 KB	Output is correct
3	Correct	70 ms	125944 KB	Output is correct
4	Correct	75 ms	125944 KB	Output is correct
5	Incorrect	70 ms	125944 KB	Output isn't correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	71 ms	126080 KB	Output is correct
2	Correct	70 ms	126136 KB	Output is correct
3	Correct	70 ms	126076 KB	Output is correct
4	Correct	70 ms	126020 KB	Output is correct
5	Correct	1669 ms	181380 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	126072 KB	Output is correct
2	Correct	2343 ms	174628 KB	Output is correct
3	Correct	2387 ms	174572 KB	Output is correct
4	Correct	2335 ms	174812 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	126072 KB	Output is correct
2	Correct	2343 ms	174628 KB	Output is correct
3	Correct	2387 ms	174572 KB	Output is correct
4	Correct	2335 ms	174812 KB	Output is correct
5	Correct	71 ms	125944 KB	Output is correct
6	Correct	2349 ms	174808 KB	Output is correct
7	Correct	2394 ms	174812 KB	Output is correct
8	Correct	2356 ms	174912 KB	Output is correct
9	Correct	2416 ms	174980 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	126072 KB	Output is correct
2	Correct	2343 ms	174628 KB	Output is correct
3	Correct	2387 ms	174572 KB	Output is correct
4	Correct	2335 ms	174812 KB	Output is correct
5	Correct	68 ms	125948 KB	Output is correct
6	Correct	292 ms	131816 KB	Output is correct
7	Correct	290 ms	131816 KB	Output is correct
8	Correct	287 ms	131944 KB	Output is correct
9	Correct	287 ms	131816 KB	Output is correct
10	Correct	291 ms	131944 KB	Output is correct
11	Correct	304 ms	131820 KB	Output is correct
12	Correct	292 ms	131820 KB	Output is correct
13	Correct	294 ms	131816 KB	Output is correct
14	Correct	296 ms	131816 KB	Output is correct
15	Correct	297 ms	131816 KB	Output is correct
16	Correct	300 ms	131816 KB	Output is correct
17	Correct	289 ms	131816 KB	Output is correct
18	Correct	2319 ms	174612 KB	Output is correct
19	Correct	2287 ms	174632 KB	Output is correct
20	Correct	2442 ms	174568 KB	Output is correct
21	Correct	304 ms	131816 KB	Output is correct
22	Correct	286 ms	131944 KB	Output is correct
23	Correct	818 ms	148064 KB	Output is correct

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	68 ms	125944 KB	Output is correct
2	Correct	299 ms	131756 KB	Output is correct
3	Correct	295 ms	131816 KB	Output is correct
4	Correct	2463 ms	174932 KB	Output is correct
5	Correct	298 ms	131944 KB	Output is correct
6	Correct	302 ms	131816 KB	Output is correct
7	Correct	307 ms	131816 KB	Output is correct
8	Correct	303 ms	131816 KB	Output is correct
9	Correct	300 ms	131816 KB	Output is correct
10	Correct	315 ms	131816 KB	Output is correct
11	Correct	306 ms	131816 KB	Output is correct
12	Correct	291 ms	131820 KB	Output is correct
13	Correct	309 ms	131816 KB	Output is correct
14	Correct	2406 ms	174572 KB	Output is correct
15	Correct	299 ms	131816 KB	Output is correct
16	Correct	2282 ms	174744 KB	Output is correct
17	Correct	2305 ms	174668 KB	Output is correct
18	Incorrect	70 ms	125944 KB	Output isn't correct

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	69 ms	126032 KB	Output is correct
2	Correct	90 ms	126740 KB	Output is correct
3	Correct	92 ms	126836 KB	Output is correct
4	Correct	68 ms	125964 KB	Output is correct
5	Correct	67 ms	125944 KB	Output is correct
6	Correct	69 ms	125944 KB	Output is correct
7	Correct	74 ms	125944 KB	Output is correct
8	Correct	78 ms	126072 KB	Output is correct
9	Correct	67 ms	125944 KB	Output is correct
10	Correct	74 ms	125944 KB	Output is correct
11	Correct	75 ms	125944 KB	Output is correct
12	Correct	72 ms	125948 KB	Output is correct
13	Correct	73 ms	125944 KB	Output is correct
14	Correct	68 ms	125944 KB	Output is correct
15	Correct	78 ms	125944 KB	Output is correct
16	Correct	97 ms	126836 KB	Output is correct
17	Correct	305 ms	131820 KB	Output is correct
18	Incorrect	67 ms	125944 KB	Output isn't correct

Submission #252134

Compilation message