oj.uz

Submission #404922

# Submission time Handle Problem Language Result Execution time Memory
404922 2021-05-15T10:06:28 Z A_D Strange Device (APIO19_strange_device) C++14
5 / 100
 588 ms 70300 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";
    int ans=0;
    for(int j=0;j<l.size();j++){
//        cout<<l[j]<<" "<<r[j]<<endl;
        ans+=r[j]-l[j]+1;
    }
  //  cout<<"\n\n";
//    cout<<st.size()<<endl;
    cout<<ans<<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:56: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]
   56 |     for(int j=0;j<l.size();j++){
      |                 ~^~~~~~~~~
strange_device.cpp: At global scope:
strange_device.cpp:65:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   65 | 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
0 / 10.0

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

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
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 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 372 ms 31692 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 541 ms 53092 KB Output is correct
3 Incorrect 504 ms 53008 KB Output isn't correct
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 541 ms 53092 KB Output is correct
3 Incorrect 504 ms 53008 KB Output isn't correct
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 541 ms 53092 KB Output is correct
3 Incorrect 504 ms 53008 KB Output isn't correct
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 Correct 54 ms 6448 KB Output is correct
3 Correct 58 ms 6420 KB Output is correct
4 Correct 588 ms 53784 KB Output is correct
5 Correct 61 ms 10092 KB Output is correct
6 Correct 55 ms 9968 KB Output is correct
7 Correct 55 ms 10004 KB Output is correct
8 Correct 55 ms 10032 KB Output is correct
9 Correct 58 ms 9960 KB Output is correct
10 Correct 54 ms 9976 KB Output is correct
11 Correct 71 ms 10012 KB Output is correct
12 Correct 50 ms 10012 KB Output is correct
13 Correct 65 ms 10000 KB Output is correct
14 Correct 549 ms 70300 KB Output is correct
15 Incorrect 57 ms 10036 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 204 KB Output is correct
2 Correct 7 ms 840 KB Output is correct
3 Correct 8 ms 840 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -