oj.uz

Submission #404923

# Submission time Handle Problem Language Result Execution time Memory
404923 2021-05-15T10:08:05 Z A_D Strange Device (APIO19_strange_device) C++14
0 / 100
 612 ms 53156 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});
            b.push_back({(int)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];
        ans++;
    }
  //  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:66:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   66 | 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 8 ms 840 KB Output is correct
3 Incorrect 6 ms 840 KB Output isn't correct
4 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
0 / 5.0

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

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 540 ms 53088 KB Output is correct
3 Incorrect 557 ms 53156 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 540 ms 53088 KB Output is correct
3 Incorrect 557 ms 53156 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 540 ms 53088 KB Output is correct
3 Incorrect 557 ms 53156 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 58 ms 6240 KB Output is correct
3 Correct 70 ms 6388 KB Output is correct
4 Correct 612 ms 53088 KB Output is correct
5 Correct 60 ms 6352 KB Output is correct
6 Correct 55 ms 6328 KB Output is correct
7 Correct 55 ms 6316 KB Output is correct
8 Correct 79 ms 6332 KB Output is correct
9 Correct 55 ms 6356 KB Output is correct
10 Correct 57 ms 6344 KB Output is correct
11 Correct 57 ms 6308 KB Output is correct
12 Incorrect 54 ms 6244 KB Output isn't correct
13 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 8 ms 840 KB Output is correct
3 Incorrect 6 ms 840 KB Output isn't correct
4 Halted 0 ms 0 KB -