Submission #660564

#	Time	Username	Problem	Language	Result	Execution time	Memory
660564		600Mihnea	trapezoid (balkan11_trapezoid)	C++17	100 / 100	133 ms	13024 KiB

trapezoid

bool home = 0;

#include <bits/stdc++.h>

using namespace std;

const int MODULO = 30013;

struct T
{
  int a;
  int b;
  int c;
  int d;
};

bool operator < (T first, T second)
{
  return first.a < second.a;
}

struct P
{
  int dp;
  int cnt;
};

P operator + (P a, P b)
{
  if (a.dp > b.dp)
  {
    return a;
  }
  if (a.dp < b.dp)
  {
    return b;
  }
  return {a.dp, (a.cnt + b.cnt) % MODULO};
}

int main()
{
  if (home == 0)
  {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  }
  else
  {
    freopen ("input.txt", "r", stdin);
  }

  int n;
  cin >> n;
  vector<T> v(n);
  map<int, int> mp;

  for (auto &it : v)
  {
    cin >> it.a >> it.b >> it.c >> it.d;
    it.c--;
    mp[it.c] = 0;
    mp[it.d] = 0;
  }
  int yahor = 0;
  for (auto &it : mp)
  {
    it.second = ++yahor;
  }
  for (auto &it : v)
  {
    it.c = mp[it.c];
    it.d = mp[it.d];
  }
  sort(v.begin(), v.end());
  vector<P> fw(yahor + 1);
  vector<int> iB(n);
  iota(iB.begin(), iB.end(), 0);
  sort(iB.begin(), iB.end(), [&] (int i, int j) {
    return v[i].b < v[j].b;
  });
  int ptr = 0;
  vector<int> dp(n, 0), ways(n, 0);
  for (int i = 0; i < n; i++)
  {
    while (ptr < n && v[iB[ptr]].b < v[i].a)
    {
      for (int x = v[iB[ptr]].d; x <= yahor; x += x & (-x))
      {
        fw[x] = fw[x] + P{dp[iB[ptr]] + 1, ways[iB[ptr]]};
      }
      ptr++;
    }
    P sol = {1, 1};
    for (int x = v[i].c; x; x -= x & (-x))
    {
      sol = sol + fw[x];
    }
    dp[i] = sol.dp;
    ways[i] = sol.cnt;
  }
  int mx = *max_element(dp.begin(), dp.end()), cnt = 0;
  for (int i = 0; i < n; i++)
  {
    if (dp[i] == mx)
    {
      cnt = (cnt + ways[i]) % MODULO;
    }
  }
  cout << mx << " " << cnt << "\n";
  return 0;
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:49:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     freopen ("input.txt", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100