oj.uz

Submission #209206

# Submission time Handle Problem Language Result Execution time Memory
209206 2020-03-13T11:57:43 Z AryaKnight Exhibition (JOI19_ho_t2) C++14
0 / 100
 5 ms 376 KB 
//#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
//#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
//#pragma GCC target("avx2")  //Enable AVX
#include<bits/stdc++.h>
using namespace std;

#define all(a) begin(a),end(a)
#define F first
#define S second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

void clr(auto &a,int n){
  a.clear();
  a.resize(n);
}

template <typename A, typename B>
istream& operator>>(istream& input,pair<A,B>& x) {
  input>>x.F>>x.S;
  return input;
}

template <typename A>
istream& operator>>(istream& input,vector<A>& x) {
  for(auto& i:x)
    input>>i;
  return input;
}

template<typename A>
ostream& operator<<(ostream& output,vector<A>& x) {
  for(auto& i:x)
    output<<i<<' ';
  return output;
}

template<typename T>
vector<pair<T,int>> getvec(int n){
  vector<pair<T,int>>a(n);
  for(int i=0;i<a.size();i++){
    cin>>a[i].F;
    a[i].S=i;
  }
  return a;
}

const int mod=1e9+7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int mul(int a,int b){
  return ((a)*1ll*(b))%mod;
}

void add(int &a,int b){
  a+=b;
  if(a>=mod)a-=mod;
}

int sub(int a,int b){
  a-=b;
  if(a<0){
    a+=mod;
  }
  return a;
}

int powz(int a,int b){
  int res=1;
  while(b){
    if(b&1){
      res=mul(res,a);
    }
    b/=2;
    a=mul(a,a);
  }
  return res;
}

const int N=200005;

struct SegTree{
  vector<int>t;
  int _=0;
  int merge(int x,int y){
    return max(x,y);
  }
  SegTree(int n){
    t.resize(4*n);
    for(auto &i:t){
      i=_;
    }
  }
  
  int query(int v, int tl, int tr, int l, int r) {
    if (l > r) 
      return _;
    if (l == tl && r == tr) {
      return t[v];
    }
    int tm = (tl + tr) / 2;
    return merge(query(v*2, tl, tm, l, min(r, tm))
		 ,query(v*2+1, tm+1, tr, max(l, tm+1), r));
  }
  
  void update(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
      t[v] = new_val;
    } else {
      int tm = (tl + tr) / 2;
      if (pos <= tm)
	update(v*2, tl, tm, pos, new_val);
      else
	update(v*2+1, tm+1, tr, pos, new_val);
      t[v] = merge(t[v*2],t[v*2+1]);
    }
  }
}; 

void solve(){
  int n,m;
  cin>>n>>m;
  vector<pair<int,int>>a(n);
  for(auto &i:a){
    cin>>i.S>>i.F;
  }
  sort(all(a));
  vi c(m);
  cin>>c;
  sort(all(c));
  vector<int>compress;
  for(auto &i:a){
    compress.pb(i.S);
  }
  for(auto &i:c){
    compress.pb(i);
  }
  sort(all(compress));
  compress.resize(unique(all(compress))-compress.begin());
  for(auto &i:a){
    i.S=lower_bound(all(compress),i.S)-compress.begin();
  }
  for(auto &i:c){
    i=lower_bound(all(compress),i)-compress.begin();
  }
  SegTree st(n+1);
  int lst=0,ans=0;
  for(int i=0;i<n;i++){
    int it=lower_bound(all(c),a[i].S)-c.begin();
    if(it<lst){
      it=lst;
    }
    if(it!=c.size()){
      ans++;
      lst=it+1;
    }
  }
  cout<<ans;
  
}

signed main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int tc=1;
  //cin>>tc;
  for(int _=0;_<tc;_++){
    // cout<<"Case #"<<_+1<<": ";
    solve();
    if(_!=tc-1){
      cout<<'\n';
    }
  }
}

Compilation message

joi2019_ho_t2.cpp: In function 'void solve()':
joi2019_ho_t2.cpp:163:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(it!=c.size()){
        ~~^~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 40.0

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

Subtask #3
0 / 50.0

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