oj.uz

Submission #547584

# Submission time Handle Problem Language Result Execution time Memory
547584 2022-04-11T03:12:06 Z LittleFlowers__ Strange Device (APIO19_strange_device) C++17
35 / 100
 395 ms 53184 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(false),cin.tie(nullptr);
#define task "A"
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))
main(){
    //freopen(task".inp","r",stdin);
    //freopen(task".out","w",stdout);
    int n=in,a=in,b=in,sz=a/__gcd(a,b+1)*b;
    vector<ii> tmp;
    forinc(i,1,n){
        int l=in,r=in;
        if(r-l+1>sz) return cout<<sz,0;
        l=l%sz; r=r%sz;
        if(l<=r) tmp.pb({l,r});
        else tmp.pb({l,sz-1}),tmp.pb({0,r});
    }
    sort(all(tmp));
    int ret=0;
    forinc(i,0,tmp.size()-1){
        int j=i,hold=tmp[i].se;
        while(j<tmp.size() && tmp[j].fi<=hold){
            hold=max(hold,tmp[j].se);
            j++;
        }
        ret+=hold-tmp[i].fi+1;
        i=j-1;
    }
    cout<<ret;
}

Compilation message

strange_device.cpp:22:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   22 | main(){
      | ^~~~
strange_device.cpp: In function 'int main()':
strange_device.cpp:38:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         while(j<tmp.size() && tmp[j].fi<=hold){
      |               ~^~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 956 KB Output is correct
3 Correct 3 ms 960 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 304 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 4 ms 1064 KB Output is correct
17 Correct 29 ms 5624 KB Output is correct
18 Incorrect 0 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 164 ms 41156 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 269 ms 35660 KB Output is correct
3 Correct 235 ms 23432 KB Output is correct
4 Correct 229 ms 23424 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 269 ms 35660 KB Output is correct
3 Correct 235 ms 23432 KB Output is correct
4 Correct 229 ms 23424 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 233 ms 24156 KB Output is correct
7 Correct 248 ms 24288 KB Output is correct
8 Correct 245 ms 24180 KB Output is correct
9 Correct 395 ms 24120 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 269 ms 35660 KB Output is correct
3 Correct 235 ms 23432 KB Output is correct
4 Correct 229 ms 23424 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 25 ms 5648 KB Output is correct
7 Correct 27 ms 5600 KB Output is correct
8 Correct 24 ms 5624 KB Output is correct
9 Correct 25 ms 5652 KB Output is correct
10 Correct 25 ms 5656 KB Output is correct
11 Correct 25 ms 5596 KB Output is correct
12 Correct 26 ms 5648 KB Output is correct
13 Correct 26 ms 5672 KB Output is correct
14 Correct 25 ms 5676 KB Output is correct
15 Correct 29 ms 5624 KB Output is correct
16 Correct 27 ms 5628 KB Output is correct
17 Correct 26 ms 5688 KB Output is correct
18 Correct 288 ms 53148 KB Output is correct
19 Correct 242 ms 53184 KB Output is correct
20 Correct 302 ms 53128 KB Output is correct
21 Correct 28 ms 5688 KB Output is correct
22 Correct 23 ms 5652 KB Output is correct
23 Correct 76 ms 18472 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 31 ms 5632 KB Output is correct
3 Correct 27 ms 5656 KB Output is correct
4 Correct 326 ms 36336 KB Output is correct
5 Correct 28 ms 5692 KB Output is correct
6 Correct 29 ms 5676 KB Output is correct
7 Correct 28 ms 5616 KB Output is correct
8 Correct 28 ms 5636 KB Output is correct
9 Correct 28 ms 5692 KB Output is correct
10 Correct 30 ms 5660 KB Output is correct
11 Correct 28 ms 5704 KB Output is correct
12 Correct 23 ms 5608 KB Output is correct
13 Correct 28 ms 5616 KB Output is correct
14 Correct 290 ms 36368 KB Output is correct
15 Correct 28 ms 5688 KB Output is correct
16 Correct 241 ms 36208 KB Output is correct
17 Correct 257 ms 35808 KB Output is correct
18 Incorrect 0 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 956 KB Output is correct
3 Correct 3 ms 960 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 304 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 4 ms 1064 KB Output is correct
17 Correct 29 ms 5624 KB Output is correct
18 Incorrect 0 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -