oj.uz

Submission #742732

# Submission time Handle Problem Language Result Execution time Memory
742732 2023-05-16T20:11:25 Z speedyArda Strange Device (APIO19_strange_device) C++14
10 / 100
 2294 ms 157072 KB 
#include "bits/stdc++.h"

using namespace std;
using ll = long long;
const int MAXN = 2e6+5;
map<ll, bool> visited;
vector< pair<ll, ll> > imp;
ll n, a, b;

int main() 
{
    cin >> n >> a >> b;
    ll sum = 0;
    ll big = 1;
   
    if(2e18 / b < a)
        big = 2e18;
    else
        big = a * b;
    for(int i = 1; i <= n; i++)
    {

        ll f, s;
        cin >> f >> s;

        if(s - f >= big - 1)
        {
            imp.push_back({0, 1});
            imp.push_back({big - 1, 2});
        } else 
        {
            if(f % big <= s % big)
            {
                imp.push_back({f % big, 1});
                imp.push_back({s % big, 2});
            } else 
            {
                imp.push_back({0, 1});
                imp.push_back({s % big, 2});
                imp.push_back({f % big, 1});
                imp.push_back({big - 1, 2});
            }

        }

       
    }

   // cout << seg[0].sum << "\n";
    sort(imp.begin(), imp.end());
        ll cnt = 0;
        ll ans = 0;
        ll last = -1;
        for(pair<ll, ll> e : imp)
        {
            //cout << ans << " " << cnt << " " << last << "\n";
            if(last != -1 && cnt > 0)
            {
                ans += e.first - last;
                if(!visited[last])
                {
                    ans++;
                    visited[last] = true;
                }
                visited[e.first] = true;
            }
            if(e.second == 1)
            {
                cnt++;
                last = e.first;
            } else 
            {   
                cnt--;
                last = e.first;
            }   
        }
        cout << ans << "\n";
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:13:8: warning: unused variable 'sum' [-Wunused-variable]
   13 |     ll sum = 0;
      |        ^~~

Subtask #1
0 / 10.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 927 ms 33216 KB Output is correct

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 189 ms 15840 KB Output is correct
3 Correct 194 ms 15928 KB Output is correct
4 Correct 2227 ms 157072 KB Output is correct
5 Correct 190 ms 15920 KB Output is correct
6 Correct 188 ms 15868 KB Output is correct
7 Correct 192 ms 15960 KB Output is correct
8 Correct 184 ms 15916 KB Output is correct
9 Correct 187 ms 15840 KB Output is correct
10 Correct 185 ms 15868 KB Output is correct
11 Correct 189 ms 15932 KB Output is correct
12 Correct 176 ms 15928 KB Output is correct
13 Correct 191 ms 15972 KB Output is correct
14 Correct 2294 ms 156868 KB Output is correct
15 Incorrect 187 ms 15916 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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