oj.uz

Submission #659133

# Submission time Handle Problem Language Result Execution time Memory
659133 2022-11-16T17:16:57 Z activedeltorre Strange Device (APIO19_strange_device) C++14
20 / 100
 1682 ms 141304 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;
map<long long,long long>norm;
vector<pair<long long,long long> >vec[2000005];
bool cmp(pair<long long,long long> a,pair<long long,long long>b)
{
    if(a.first!=b.first)
    {
        return a.first<b.first;
    }
    return a.second>b.second;
}
int main()
{
    long long n,i,j,m,k,l,a,b,val1,val2,rest1,rest2,valoare,cnt=0,x,y;
    cin>>n>>a>>b;
    for(i=1; i<=n; i++)
    {
        cin>>x>>y;
        val1=x/b;
        val2=y/b;
        rest1=x%b;
        rest2=y%b;
        if(val1==val2)
        {
            valoare=(val1*(b+1))%a;
            if(norm[valoare]==0)
            {
                cnt++;
                norm[valoare]=cnt;
            }
            vec[norm[valoare]].push_back({rest1,rest2});
        }
        else
        {
            valoare=(val1*(b+1))%a;
            if(norm[valoare]==0)
            {
                cnt++;
                norm[valoare]=cnt;
            }
            vec[norm[valoare]].push_back({rest1,b-1});
            valoare=(val2*(b+1))%a;
            if(norm[valoare]==0)
            {
                cnt++;
                norm[valoare]=cnt;
            }
            vec[norm[valoare]].push_back({0,rest2});
        }
    }
    long long suma=0,nr,dr,index;
    for(i=1; i<=cnt; i++)
    {
        sort(vec[i].begin(),vec[i].end(),cmp);
        nr=vec[i].size();
        for(j=0; j<nr; j++)
        {
            index=j;
            dr=vec[i][j].second;
            while(index+1<nr && dr>=vec[i][index+1].first)
            {
                dr=max(dr,vec[i][index+1].second);
                index++;
            }
            suma=suma+dr-vec[i][j].first+1;
            j=index;
        }
    }
    cout<<suma;
    return 0;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:19:21: warning: unused variable 'm' [-Wunused-variable]
   19 |     long long n,i,j,m,k,l,a,b,val1,val2,rest1,rest2,valoare,cnt=0,x,y;
      |                     ^
strange_device.cpp:19:23: warning: unused variable 'k' [-Wunused-variable]
   19 |     long long n,i,j,m,k,l,a,b,val1,val2,rest1,rest2,valoare,cnt=0,x,y;
      |                       ^
strange_device.cpp:19:25: warning: unused variable 'l' [-Wunused-variable]
   19 |     long long n,i,j,m,k,l,a,b,val1,val2,rest1,rest2,valoare,cnt=0,x,y;
      |                         ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47188 KB Output is correct
2 Correct 34 ms 47484 KB Output is correct
3 Correct 35 ms 47792 KB Output is correct
4 Incorrect 21 ms 47188 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47188 KB Output is correct
2 Correct 23 ms 47208 KB Output is correct
3 Correct 22 ms 47264 KB Output is correct
4 Incorrect 25 ms 47188 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47340 KB Output is correct
2 Incorrect 24 ms 47356 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47188 KB Output is correct
2 Incorrect 1592 ms 141144 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47188 KB Output is correct
2 Incorrect 1592 ms 141144 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47188 KB Output is correct
2 Incorrect 1592 ms 141144 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47156 KB Output is correct
2 Correct 146 ms 49132 KB Output is correct
3 Correct 146 ms 52768 KB Output is correct
4 Correct 1682 ms 141304 KB Output is correct
5 Correct 163 ms 53548 KB Output is correct
6 Correct 154 ms 53432 KB Output is correct
7 Correct 157 ms 53652 KB Output is correct
8 Correct 186 ms 55276 KB Output is correct
9 Correct 167 ms 55312 KB Output is correct
10 Correct 146 ms 52544 KB Output is correct
11 Correct 148 ms 52696 KB Output is correct
12 Correct 147 ms 52780 KB Output is correct
13 Correct 161 ms 54588 KB Output is correct
14 Correct 1284 ms 100720 KB Output is correct
15 Correct 146 ms 53308 KB Output is correct
16 Correct 1270 ms 100968 KB Output is correct
17 Correct 1639 ms 137428 KB Output is correct
18 Correct 24 ms 47188 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47188 KB Output is correct
2 Correct 34 ms 47484 KB Output is correct
3 Correct 35 ms 47792 KB Output is correct
4 Incorrect 21 ms 47188 KB Output isn't correct
5 Halted 0 ms 0 KB -