oj.uz

Submission #940357

# Submission time Handle Problem Language Result Execution time Memory
940357 2024-03-07T08:26:17 Z emad234 trapezoid (balkan11_trapezoid) C++17
100 / 100
 100 ms 23116 KB 
#include <bits/stdc++.h>
#define all(v) ((v).begin(),(v).end())
#define F first
#define S second
typedef long long ll;
#define pii pair<ll,ll>
using namespace std;
const ll mod = 30013;
const ll mxN = 4e6 + 5;
struct poll{
  ll u,d,id;
};
bool operator<(poll a,poll b){
  return a.u < b.u;
}
pii combine(pii a, pii b){
  if(a.F == b.F) return {a.F,(a.S + b.S) % mod};
  return max(a,b);
}
vector<poll>a;
bool vis[mxN];
pii dp[mxN];
pii seg[mxN];
ll s,e,N;
pii query(ll l = 1,ll r = N,ll ind = 1){
  if(l > e || r < s) return {0,0};
  if(l >= s && r <= e) return seg[ind];
  ll md = (l +r) / 2;
  return combine(query(l,md,ind * 2),query(md + 1,r,ind * 2 + 1));
}
void update(ll ind,pii val){
  ind += N;
  seg[ind] = val;
  while(ind /= 2){
    seg[ind] = combine(seg[ind * 2],seg[ind * 2 + 1]);
  }
}
signed main(){
  ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
  vector<ll>c;
  ll n;
  cin >>n;
  for(ll i = 0;i < n;i++){
    ll x,x1,y,y1;
    cin >>x>>x1>>y>>y1;
    a.push_back({x,y,i});
    a.push_back({x1,y1,i});
  }
  sort(a.begin(),a.end());
  for(auto x : a){
    c.push_back(x.d);
  }
  ll mx = 0;
  sort(c.begin(),c.end());
  for(auto &x: a){
    x.d = lower_bound(c.begin(),c.end(),x.d) - c.begin() + 1;
    mx = max(mx,x.d);
  }
  N = exp2(ceil(log2(mx + 1)));
  pii ans = {0,0};
  for(auto x : a){
    if(!vis[x.id]){
      s = 1;e = x.d;
      pii ch = query();
      ch.F++;
      dp[x.id] = combine(ch,{1,1});
      ans = combine(ans,dp[x.id]);
    }else{
      update(x.d,dp[x.id]);
    }
    vis[x.id] = 1;
  }
  cout<<ans.F<<' '<<ans.S<<'\n';
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2512 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 3 ms 4892 KB Output is correct
7 Correct 5 ms 5052 KB Output is correct
8 Correct 5 ms 3160 KB Output is correct
9 Correct 10 ms 4308 KB Output is correct
10 Correct 16 ms 6092 KB Output is correct
11 Correct 24 ms 6608 KB Output is correct
12 Correct 55 ms 11720 KB Output is correct
13 Correct 60 ms 12736 KB Output is correct
14 Correct 74 ms 16848 KB Output is correct
15 Correct 79 ms 18616 KB Output is correct
16 Correct 85 ms 19164 KB Output is correct
17 Correct 94 ms 19860 KB Output is correct
18 Correct 70 ms 23116 KB Output is correct
19 Correct 90 ms 22300 KB Output is correct
20 Correct 100 ms 23068 KB Output is correct