oj.uz

Submission #404919

# Submission time Handle Problem Language Result Execution time Memory
404919 2021-05-15T10:03:47 Z A_D Strange Device (APIO19_strange_device) C++14
15 / 100
 3151 ms 524292 KB 
#include <bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define F first
#define S second
#define du long double
using namespace std;
const int N=1e6+100;
ii a[N];
vector<int> l;
vector<int> r;
vector<ii> b;
set<ii> st;
void solve()
{
    int n,A,B;
    cin>>n>>A>>B;
    int u=A*B;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i].F);
        scanf("%lld",&a[i].S);
        a[i].F%=u;
        a[i].S%=u;
//        cout<<a[i].F<<" "<<a[i].S<<endl;
        if(a[i].S<a[i].F){
            b.push_back({a[i].F,u-1});
            b.push_back({0,a[i].S});
        }
        else{
            b.push_back({a[i].F,a[i].S});
        }
    }
    sort(b.begin(),b.end());
    l.push_back(b[0].F);
    r.push_back(b[0].S);
    for(int i=1;i<b.size();i++){
  //      cout<<b[i].F<<" "<<b[i].S<<endl;
        int ll=l.back();
        int rr=r.back();
        if(!(ll>b[i].S||rr<b[i].F)){
    //        cout<<ll<<" "<<rr<<" "<<b[i].F<<" "<<b[i].S<<endl;
            l.pop_back();
            r.pop_back();
            l.push_back(min(ll,b[i].F));
            r.push_back(max(rr,b[i].S));
        }
        else{
            l.push_back(b[i].F);
            r.push_back(b[i].S);
        }
    }
//    cout<<"\n\n";
  //  for(int i=0;i<l.size();i++)cout<<l[i]<<" "<<r[i]<<endl;
    //cout<<"\n\n";
    for(int j=0;j<l.size();j++){
//        cout<<l[j]<<" "<<r[j]<<endl;
        for(int i=l[j];i<=r[j];i++){
            int x=(i+(i/B))%A;
            int y=i%B;
            st.insert({x,y});
        }
    }
  //  cout<<"\n\n";
    cout<<st.size()<<endl;
}

main()
{
    int t=1;
    //cin>>t;
    while(t--)solve();
}

Compilation message

strange_device.cpp: In function 'void solve()':
strange_device.cpp:36:18: 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]
   36 |     for(int i=1;i<b.size();i++){
      |                 ~^~~~~~~~~
strange_device.cpp:55:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int j=0;j<l.size();j++){
      |                 ~^~~~~~~~~
strange_device.cpp: At global scope:
strange_device.cpp:67:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   67 | main()
      | ^~~~
strange_device.cpp: In function 'void solve()':
strange_device.cpp:20:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         scanf("%lld",&a[i].F);
      |         ~~~~~^~~~~~~~~~~~~~~~
strange_device.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf("%lld",&a[i].S);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 57 ms 12964 KB Output is correct
3 Correct 71 ms 18512 KB Output is correct
4 Correct 2 ms 808 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 424 KB Output is correct
8 Correct 1 ms 428 KB Output is correct
9 Correct 4 ms 1196 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 256 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 27 ms 7012 KB Output is correct
16 Correct 33 ms 7364 KB Output is correct
17 Correct 81 ms 11440 KB Output is correct
18 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Runtime error 2945 ms 524292 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 116 ms 32312 KB Output is correct
3 Correct 157 ms 32044 KB Output is correct
4 Correct 117 ms 30648 KB Output is correct
5 Correct 739 ms 93920 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 808 ms 110276 KB Output is correct
3 Runtime error 3151 ms 524292 KB Execution killed with signal 9
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 808 ms 110276 KB Output is correct
3 Runtime error 3151 ms 524292 KB Execution killed with signal 9
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 808 ms 110276 KB Output is correct
3 Runtime error 3151 ms 524292 KB Execution killed with signal 9
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 Runtime error 1774 ms 524292 KB Execution killed with signal 9
3 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 Correct 57 ms 12964 KB Output is correct
3 Correct 71 ms 18512 KB Output is correct
4 Correct 2 ms 808 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 424 KB Output is correct
8 Correct 1 ms 428 KB Output is correct
9 Correct 4 ms 1196 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 256 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 27 ms 7012 KB Output is correct
16 Correct 33 ms 7364 KB Output is correct
17 Correct 81 ms 11440 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Runtime error 2945 ms 524292 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -