oj.uz

Submission #1092249

# Submission time Handle Problem Language Result Execution time Memory
1092249 2024-09-23T15:59:30 Z NguyenPhucThang trapezoid (balkan11_trapezoid) C++14
43 / 100
 117 ms 18944 KB 
#include <bits/stdc++.h>
#define forr(i, a, b) for (int i = (a); i <= (b); i++)
#define ford(i, a, b) for (int i = (a); i >= (b); i--)
#define forf(i, a, b) for (int i = (a); i < (b); i++)
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vii vector<pii>
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "trapezoid"

using namespace std;
const int base = 31;
const ll mod = 30013;
const ll oo = 1e18;
const int N = 1e6 + 5;

struct event{
   int x, y, type, idx;

   bool operator < (const event &other){
      if (x == other.x) return y < other.y;
      return x < other.x;
   }
};


pll st[4 * N];

pll combine(pll a, pll b){
   if (a.fi == b.fi) return {a.fi, (a.se + b.se) % mod};
   return (a.fi < b.fi ? b : a);
}


void update(int id, int l, int r, int i, pll v){
   if (i < l || r < i) return;
   if (l == r){
      st[id] = combine(st[id], v);
      return;
   }

   int mid = (l + r) >> 1;
   update(2 * id, l, mid, i, v), update(2 * id + 1, mid + 1, r, i, v);
   st[id] = combine(st[2 * id], st[2 * id + 1]);
}

pll get(int id, int l, int r, int u, int v){
   if (v < l || r < u) return {0, 1};
   if (u <= l && r <= v) return st[id];
   int mid = (l + r) >> 1;
   return combine(get(2 * id, l, mid, u, v), get(2 * id + 1, mid + 1, r, u, v));
}

ll dp[N], cnt[N];

int main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);

   int n;
   cin >> n;
   vector<event> v;
   vector<int> nen;
   forr(i, 1, n) {
      int a, b, c, d;
      cin >> a >> b >> c >> d;
      if (a > b) swap(a, b);
      if (c > d) swap(c, d);  
      v.pb({a, c, 0, i});
      v.pb({b, d, 1, i});  
      nen.pb(c);
      nen.pb(d);
   }

   sort(all(nen));
   nen.resize(unique(all(nen)) - nen.begin());
   forf(i, 0, v.size()) {
      v[i].y = lower_bound(all(nen), v[i].y) - nen.begin() + 1;
   }

   sort(all(v));

   forf(i, 0, v.size()){
      if (v[i].type == 0){
         pll ans = get(1, 1, 4e5, 1, v[i].y - 1);
         int id = v[i].idx;
         dp[id] = ans.fi + 1;
         if (dp[id] == 1) cnt[id] = 1;
         else cnt[id] = ans.se;
      }
      else {
         int id = v[i].idx;
         update(1, 1, 4e5, v[i].y, {dp[id], cnt[id]});
      }
   }  

   int res_dp = 0, res_cnt;
   forr(i, 1, n) if (res_dp < dp[i]) res_dp = dp[i], res_cnt = cnt[i];
   cout << res_dp << " " << res_cnt;

   return 0;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:4:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forf(i, a, b) for (int i = (a); i < (b); i++)
      |                                           ^
trapezoid.cpp:87:4: note: in expansion of macro 'forf'
   87 |    forf(i, 0, v.size()) {
      |    ^~~~
trapezoid.cpp:4:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forf(i, a, b) for (int i = (a); i < (b); i++)
      |                                           ^
trapezoid.cpp:93:4: note: in expansion of macro 'forf'
   93 |    forf(i, 0, v.size()){
      |    ^~~~
trapezoid.cpp:109:29: warning: 'res_cnt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  109 |    cout << res_dp << " " << res_cnt;
      |                             ^~~~~~~

Subtask #1
43.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 4440 KB Partially correct
2 Partially correct 1 ms 4444 KB Partially correct
3 Partially correct 1 ms 2652 KB Partially correct
4 Partially correct 1 ms 2652 KB Partially correct
5 Partially correct 2 ms 2652 KB Partially correct
6 Partially correct 3 ms 2860 KB Partially correct
7 Partially correct 4 ms 3164 KB Partially correct
8 Partially correct 6 ms 3172 KB Partially correct
9 Partially correct 11 ms 3824 KB Partially correct
10 Partially correct 21 ms 5396 KB Partially correct
11 Partially correct 29 ms 7700 KB Partially correct
12 Partially correct 57 ms 13320 KB Partially correct
13 Correct 73 ms 12392 KB Output is correct
14 Partially correct 81 ms 14880 KB Partially correct
15 Partially correct 93 ms 15096 KB Partially correct
16 Partially correct 98 ms 17400 KB Partially correct
17 Partially correct 104 ms 16120 KB Partially correct
18 Partially correct 94 ms 16380 KB Partially correct
19 Partially correct 107 ms 18944 KB Partially correct
20 Partially correct 117 ms 17980 KB Partially correct