oj.uz

Submission #403366

# Submission time Handle Problem Language Result Execution time Memory
403366 2021-05-13T05:47:16 Z Hazem Strange Device (APIO19_strange_device) C++14
5 / 100
 609 ms 49632 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define LL long long
#define F first
#define S second
#define pii pair<int,int>
#define piii pair<pair<int,int>,int>

const int N = 1e6+10;
const int M = 200;
const LL INF = 1e9;
const LL LINF = 2e18;
const LL MOD = 1e9+7;
const double PI = 3.141592653589793;

pair<LL,LL>p[N];
vector<pair<LL,LL>>vec;

struct node{

    node *l,*r;
    LL sum = 0;
    int lazy = 0;
    node():l(NULL),r(NULL){};
};

void push(node * &v,LL tl,LL tr){

    if(v==NULL||!v->lazy)return ;
    v->sum = tr-tl+1;

    if(tl!=tr){
        
        if(v->l==NULL)v->l = new node();
        if(v->r==NULL)v->r = new node();

        v->l->lazy = 1;
        v->r->lazy = 1;    
    }
    v->lazy = 0;
}

void update(node * &v,LL tl,LL tr,LL l,LL r){

    push(v,tl,tr);

    if(tl>r||tr<l)
        return ;
    
    if(v==NULL) v = new node();

    if(tl>=l&&tr<=r){
        v->lazy = 1;
        push(v,tl,tr);
        return ;
    }

    LL mid = (tl+tr)/2;
    update(v->l,tl,mid,l,r);
    update(v->r,mid+1,tr,l,r);
    v->sum = (v->l==NULL?0:v->l->sum)+(v->r==NULL?0:v->r->sum);
}

node *root;

int main(){

    //freopen("out.txt","w",stdout);

    LL n,a,b,Len;
    scanf("%lld%lld%lld",&n,&a,&b);

    if(log(a)+log(b)>=log(LLONG_MAX))    
        Len = LINF;
    else 
        Len = a*b;

    bool q = 0;
    for(int i=1;i<=n;i++){

        scanf("%lld%lld",&p[i].F,&p[i].S);
        q |= p[i].S-p[i].F+1>=Len;

        p[i].F %= Len;p[i].S %= Len;
        
        if(p[i].S>=p[i].F)
            vec.push_back({p[i].F,p[i].S});
        else 
            vec.push_back({p[i].F,Len-1}),vec.push_back({0,p[i].S});
    }

    sort(vec.begin(),vec.end());
    
    LL l = 0,r = -1,ans = 0;
    vec.push_back({LINF,LINF});
    
    for(int i=0;i<vec.size();i++){
        
        if(vec[i].F>r)
            ans += r-l+1,l = vec[i].F,r = vec[i].S;
        else 
            r = vec[i].S;
    }

    printf("%lld\n",q?Len:ans);
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:98:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for(int i=0;i<vec.size();i++){
      |                 ~^~~~~~~~~~~
strange_device.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     scanf("%lld%lld%lld",&n,&a,&b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         scanf("%lld%lld",&p[i].F,&p[i].S);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 6 ms 716 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 529 ms 31608 KB Output is correct
3 Incorrect 548 ms 49544 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 529 ms 31608 KB Output is correct
3 Incorrect 548 ms 49544 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 529 ms 31608 KB Output is correct
3 Incorrect 548 ms 49544 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 54 ms 3492 KB Output is correct
3 Correct 54 ms 3508 KB Output is correct
4 Correct 609 ms 49536 KB Output is correct
5 Correct 55 ms 7152 KB Output is correct
6 Correct 56 ms 7144 KB Output is correct
7 Correct 75 ms 7208 KB Output is correct
8 Correct 59 ms 7160 KB Output is correct
9 Correct 56 ms 7332 KB Output is correct
10 Correct 70 ms 7192 KB Output is correct
11 Correct 56 ms 7208 KB Output is correct
12 Correct 50 ms 7180 KB Output is correct
13 Correct 56 ms 7216 KB Output is correct
14 Incorrect 572 ms 49632 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 6 ms 716 KB Output isn't correct
3 Halted 0 ms 0 KB -