Submission #106022

#	Time	Username	Problem	Language	Result	Execution time	Memory
106022		MrTEK	trapezoid (balkan11_trapezoid)	C++14	100 / 100	303 ms	20764 KiB

trapezoid

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<int,int> ii;

const int N = 1e5 + 5;
const int mod = 30013;
const int inf = 1e9;

#define ul first.first
#define ur first.second
#define dl second.first
#define dr second.second

pair <ii,ii> a[N];
int n;
ii ans,dp[N],tree[N << 3];
map <int,int> ind;
vector <ii> ep;
vector <int> v;

int add(int x,int y) {
  return x + y >= mod ? x + y - mod : x + y;
}

ii merge(ii x,ii y) {
  if (x.first == y.first)
    return {x.first,add(x.second,y.second)};
  if (x.first > y.first)
    return x;
  return y;
}

ii query(int ind,int l,int r,int lw,int rw) {
  if (l > rw || r < lw)
    return {-inf,-inf};
  if (l >= lw && r <= rw)
    return tree[ind];
  int mid = (l + r) / 2;
  return merge(query(ind + ind,l,mid,lw,rw),query(ind + ind + 1,mid + 1,r,lw,rw));
}

void update(int ind,int l,int r,int w,ii val) {
  if (l > w || r < w)
    return;
  if (l == w && r == w) {
    tree[ind] = merge(tree[ind],val);
    return;
  }
  int mid = (l + r) / 2;
  update(ind + ind,l,mid,w,val);
  update(ind + ind + 1,mid + 1,r,w,val);
  tree[ind] = merge(tree[ind + ind],tree[ind + ind + 1]);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  cin >> n;
  for (int i = 1 ; i <= n ; i++) {
    cin >> a[i].ul >> a[i].ur >> a[i].dl >> a[i].dr;
    v.push_back(a[i].dl);
    v.push_back(a[i].dr);
    ep.push_back({a[i].ur,i});
    ep.push_back({a[i].ul,i});
  }
  sort(v.begin(),v.end());
  for (int i = 0 , j = 0 ; i < v.size() ; i++) {
    if (i == 0 || v[i] != v[i - 1])
      j++;
    ind[v[i]] = j;
  }
  for (int i = 1 ; i < (N << 3) ; i++)
    tree[i] = {-inf,-inf};
  sort(ep.begin(),ep.end(),greater<ii>());
  for (auto i : ep) {
    if (a[i.second].ul == i.first)
      update(1,1,2 * n,ind[a[i.second].dl],dp[i.second]);
    else {
      ii tut = query(1,1,2 * n,ind[a[i.second].dr] + 1,2 * n);
      tut.first++;
      dp[i.second] = merge({1,1},tut);
      ans = merge(ans,dp[i.second]);
    }
  }
  cout << ans.first << " " << ans.second << endl;
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:70:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0 , j = 0 ; i < v.size() ; i++) {
                            ~~^~~~~~~~~~

• Subtask 1: 100 / 100