Submission #549410

# Submission time Handle Problem Language Result Execution time Memory
549410 2022-04-15T18:41:53 Z urosk Strange Device (APIO19_strange_device) C++14
5 / 100
699 ms 86092 KB
// __builtin_popcount(x) broj bitova
// __builtin_popcountll(x)
// __builtin_clz(x) vodece nule
// __builtin_clzll(x)
// __builtin_ctz(x) nule na pocetku
// __builtin_ctzll(x)
// 2000000011
// 2000000033
#include "bits/stdc++.h"
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 1000000000000000000LL // 10^18
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) ((ll)(a.size()))
#define all(a) a.begin(),a.end()
#define rall(a) a.begin(),a.end(),greater<int>()
#define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}
#define pi 3.14159265358979323846
#define here cerr<<"=============================================================================\n"
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define ceri2(a,l,r,n,m) {for(ll i = l;i<=r;i++){for(ll j = n;j<=m;j++) cerr<<a[i][j]<< " ";cerr<<endl;}}
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
using namespace std;
using namespace __gnu_pbds;

template<typename T> using vc = vector<T>;
template<typename T> using vvc = vc<vc<T>>;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l,ll r){
    return uniform_int_distribution<ll>(l,r)(rng);
}

void setIO(string inoutname)
{
	freopen((inoutname+".in").c_str(),"r",stdin);
    	freopen((inoutname+".out").c_str(),"w",stdout);
}
#define mod 1
ll gcd(ll a, ll b)
{
   if(b==0) return a;
   if(a==0) return b;
   if(a>=b)  return gcd(a%b,b);
   return  gcd(a,b%a);
}
ll lcm(ll a,ll b){
   return (a/gcd(a,b))*b;
}
ll add(ll x,ll y){
    x+=y;
    if(x<0){
        x%=mod;
        x+=mod;
	if(x==mod) x = 0;
    }else{
        if(x>=mod) x%=mod;
    }
    return x;
}
ll mul(ll a,ll b){
	ll ans = (a*b)%mod;
	if(ans<0) ans+=mod;
	return ans;
}
ll po(ll x,ll y){
    if(y==0) return 1LL;
    ll ans = po(x,y/2);
    ans = mul(ans,ans);
    if(y&1) ans = mul(ans,x);
    return ans;
}
ll inv(ll x){return po(x,mod-2);}
#define maxn 1000005
ll n;
pll a[maxn];
ll x,y;
void tc(){
	daj_mi_malo_vremena
    cin >> n >> x >> y;
    for(ll i = 1;i<=n;i++) cin >> a[i].fi >> a[i].sc;
    ll k = x/gcd(x,y+1);
    ll ans = 0;
    if(llinf/k<y){
        for(ll i = 1;i<=n;i++) ans+= a[i].sc-a[i].fi+1;
        cout<<ans<<endl;
        return;
    }
    ll p = k*y;
    vector<pll> v;
    bool sve = 0;
    for(ll i = 1;i<=n;i++){
        ll &l = a[i].fi;
        ll &r = a[i].sc;
        if(r-l+1>=p) sve = 1;
        l%=p;
        r%=p;
        if(r<l) sve = 1;
        v.pb({l,1});
        v.pb({r+1,-1});
    }
    if(sve){
        cout<<p<<endl;
        return;
    }
    sort(all(v));
    ll lst = -1;
    ll cnt = 0;
    for(pll p : v){
        ll i = p.fi;
        if(cnt) ans+=i-lst;
        lst = i;
        cnt+=p.sc;
    }
    cout<<ans<<endl;
    return;
}
int main(){
	daj_mi_malo_vremena
	//setIO("lol");
	int t; t = 1;
	while(t--){
		tc();
	}
	return 0;
}

Compilation message

strange_device.cpp: In function 'void setIO(std::string)':
strange_device.cpp:50:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |  freopen((inoutname+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:51:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |      freopen((inoutname+".out").c_str(),"w",stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 6 ms 1500 KB Output is correct
3 Incorrect 5 ms 1496 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 380 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 618 ms 86092 KB Output is correct
3 Incorrect 407 ms 86064 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 618 ms 86092 KB Output is correct
3 Incorrect 407 ms 86064 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 618 ms 86092 KB Output is correct
3 Incorrect 407 ms 86064 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 66 ms 9852 KB Output is correct
3 Correct 72 ms 9736 KB Output is correct
4 Correct 699 ms 86064 KB Output is correct
5 Correct 59 ms 9820 KB Output is correct
6 Correct 59 ms 9748 KB Output is correct
7 Correct 59 ms 9876 KB Output is correct
8 Correct 62 ms 9824 KB Output is correct
9 Correct 58 ms 9860 KB Output is correct
10 Correct 80 ms 9820 KB Output is correct
11 Correct 71 ms 9848 KB Output is correct
12 Incorrect 46 ms 9764 KB Output isn't correct
13 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 6 ms 1500 KB Output is correct
3 Incorrect 5 ms 1496 KB Output isn't correct
4 Halted 0 ms 0 KB -