Submission #3437310

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define _MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) _MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define pb push_back
#define all(x) begin(x),end(x)
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#ifdef LOCAL
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cerr<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cerr<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.first<<","<<p.second<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}
#else
#define dbg(...) {}
#endif

#define long long long // for codeforces

int main(){
  int n,m,l;
  cin>>n>>m>>l;
  vector<long> d(n);
  rep(i,n) cin>>d[i];

  set<long> go_all;
  vector<set<long>> go_part(n), back_part(n);
  vector<long> times;

  rep(i,m){
    long x,a;
    cin>>x>>a;
    x--;
    go_all.insert(a);
    go_part[x].insert(a);
    times.pb(a);
  }
  rep(i,l){
    long x,a;
    cin>>x>>a;
    x--;
    back_part[x].insert(a);
  }

  vector<pair<long,long>> moves; // closed range
  rep(i,n){
    for(auto s : go_part[i]){
      long arrive = s + d[i];
      auto itr = back_part[i].upper_bound(arrive);
      if(itr == back_part[i].end()) continue;
      long t = *itr + d[i];
      times.pb(s);
      times.pb(t);
      moves.pb({s,t});
    }
  }

  uniq(times);
  uniq(moves);
  const int INF = 123456789;
  vector<int> mv(times.size(), INF);
  for(auto &p : moves) {
    int s = lower_bound(all(times), p.first) - begin(times);
    int t = lower_bound(all(times), p.second) - begin(times);
    mv[s] = min(mv[s], t);
  }

  vector<int> dp(times.size()+1, 0);
  dp[0] = 0;
  rep(i,times.size()){
    if(i>0) dp[i] = max(dp[i-1], dp[i]);
    if(mv[i] < INF) dp[mv[i]+1] = max(dp[mv[i]+1], dp[i] + 2);
  }

  int ans = 0;
  rep(i,times.size()+1){
    ans = max(ans, dp[i]);
    if(i < times.size()){
      long t = times[i];
      if(go_all.lower_bound(t) != end(go_all)) ans = max(ans, dp[i]+1);
    }
  } 

  cout << ans << endl;

  return 0;
}

Submission Info

Judge Result