oj.uz

Submission #203146

# Submission time Handle Problem Language Result Execution time Memory
203146 2020-02-19T14:12:39 Z Mercenary Strange Device (APIO19_strange_device) C++14
5 / 100
 535 ms 17252 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
int n  , A , B;
const ll inf = 1e18 + 3;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> n >> A >> B;
    ll d = __gcd(A,B+1);A /= d;
    if(A > inf / B)A = inf;
    else A *= B;
    vector<pair<ll,ll>> val;
    while(n--){
        ll l ,r;cin >> l >> r;
        if(r - l + 1 >= A)tie(l,r) = mp(0,A-1);
        l %= A;r %= A;
//        cout << l << " " << r << endl;
        if(l <= r)val.pb(mp(l,r));
        else val.pb(mp(0,r)),val.pb(mp(l,A-1));
    }
    sort(val.begin(),val.end());
    ll cur = 0 , res = 0;
    for(auto c : val){
        if(cur <= c.second){
            res += c.second - max(cur,c.first) + 1;
        }
//        cout << c.first << " " <<  c.second << " " << cur << " " << res << endl;
        cur = max(cur,c.second+1);
    }
    cout << res;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:32:24: warning: overflow in implicit constant conversion [-Woverflow]
     if(A > inf / B)A = inf;
                        ^~~
strange_device.cpp:27:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:28:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 10 ms 1144 KB Output is correct
3 Correct 13 ms 1144 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 380 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 10 ms 1144 KB Output is correct
17 Correct 64 ms 5720 KB Output is correct
18 Runtime error 5 ms 504 KB Execution killed with signal 8 (could be triggered by violating memory limits)

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Runtime error 5 ms 504 KB Execution killed with signal 8 (could be triggered by violating memory limits)

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 385 ms 17176 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 535 ms 17252 KB Output is correct
3 Runtime error 6 ms 568 KB Execution killed with signal 8 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 535 ms 17252 KB Output is correct
3 Runtime error 6 ms 568 KB Execution killed with signal 8 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 535 ms 17252 KB Output is correct
3 Runtime error 6 ms 568 KB Execution killed with signal 8 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 64 ms 5736 KB Output is correct
3 Incorrect 55 ms 5740 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 10 ms 1144 KB Output is correct
3 Correct 13 ms 1144 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 380 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 10 ms 1144 KB Output is correct
17 Correct 64 ms 5720 KB Output is correct
18 Runtime error 5 ms 504 KB Execution killed with signal 8 (could be triggered by violating memory limits)