oj.uz

Submission #381737

# Submission time Handle Problem Language Result Execution time Memory
381737 2021-03-25T19:41:17 Z mohamedsobhi777 Fortune Telling 2 (JOI14_fortune_telling2) C++14
4 / 100
 3000 ms 5996 KB 
#include <bits/stdc++.h>

using namespace std;

#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define lb lower_bound
#define ub upper_bound

using ll = long long;
using ld = long double;

const int N = 6e5 + 7;
const ll mod = 1e9 + 7;

int n, k;
int act[N];

struct fenwick
{
       int bit[N];
       fenwick()
       {
              memset(bit, 0, sizeof bit);
       }
       void add(int x, int v)
       {
              ++x;
              for (; x < N; x += x & -x)
                     bit[x] += v;
       }
       int upto(int x)
       {
              ++x;
              int ret = 0;
              for (; x; x -= x & -x)
                     ret += bit[x];
              return ret;
       }
       inline int get(int l, int r) { return upto(r) - upto(l - 1); }
} f1;

int main()
{
       ios_base::sync_with_stdio(0);
       cin.tie(0);
#ifndef ONLINE_JUDGE
#endif
       cin >> n >> k;
       vii a(n);
       for (int i = 0; i < n; ++i)
              cin >> a[i].f >> a[i].s;
       vi b(k);
       for (auto &u : b)
              cin >> u;

       vector<int> v;
       for (auto u : a)
       {
              v.pb(u.f);
              v.pb(u.s);
       }
       for (auto u : b)
              v.pb(u);

       sort(all(v));

       v.erase(unique(all(v)), v.end());

       for (int i = 0; i < sz(v); ++i)
       {
              act[i] = v[i];
       }
       auto get = [&](int x) -> int {
              return lb(all(v), x) - v.begin();
       };
       for (int i = 0; i < n; ++i)
       {
              a[i].f = get(a[i].f);
              a[i].s = get(a[i].s);
       }
       for (auto &u : b)
              u = get(u);

       sort(all(a), [&](pii x, pii y) {
              return max(x.f, x.s) > max(y.f, y.s);
       });

       vii b2;
       for (int i = 0; i < k; ++i)
       {
              b2.push_back({b[i], i});
       }
       sort(all(b2));
       ll sum = 0;
       for (int i = 0; i < n; ++i)
       {

              while (sz(b2) && b2.back().f >= max(a[i].f, a[i].s))
              {
                     f1.add(b2.back().s, 1);
                     b2.pop_back();
              }

              int lst = -1;
              int L = min(a[i].f, a[i].s);
              int R = max(a[i].f, a[i].s);
              for (int j = 0; j < k; ++j)
              {
                     if (b[j] >= L && b[j] < R)
                     {
                            lst = j;
                     }
              }

              if (~lst)
              {
                     if (a[i].f < a[i].s)
                            swap(a[i].f, a[i].s);
                     if (f1.get(lst + 1, N - 2) & 1)
                     {
                            swap(a[i].f, a[i].s);
                     }
              }
              else
              {
                     if (f1.get(0, N - 2) & 1)
                     {
                            swap(a[i].f, a[i].s);
                     }
              }
              sum += act[a[i].f];
       }

       cout << sum;
       return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2668 KB Output is correct
2 Correct 4 ms 2668 KB Output is correct
3 Correct 5 ms 2796 KB Output is correct
4 Correct 5 ms 2796 KB Output is correct
5 Correct 5 ms 2796 KB Output is correct
6 Correct 5 ms 2796 KB Output is correct
7 Correct 7 ms 2796 KB Output is correct
8 Correct 4 ms 2796 KB Output is correct
9 Correct 5 ms 2796 KB Output is correct
10 Correct 5 ms 2796 KB Output is correct
11 Correct 5 ms 2796 KB Output is correct
12 Correct 5 ms 2796 KB Output is correct
13 Correct 5 ms 2796 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2668 KB Output is correct
2 Correct 4 ms 2668 KB Output is correct
3 Correct 5 ms 2796 KB Output is correct
4 Correct 5 ms 2796 KB Output is correct
5 Correct 5 ms 2796 KB Output is correct
6 Correct 5 ms 2796 KB Output is correct
7 Correct 7 ms 2796 KB Output is correct
8 Correct 4 ms 2796 KB Output is correct
9 Correct 5 ms 2796 KB Output is correct
10 Correct 5 ms 2796 KB Output is correct
11 Correct 5 ms 2796 KB Output is correct
12 Correct 5 ms 2796 KB Output is correct
13 Correct 5 ms 2796 KB Output is correct
14 Correct 282 ms 3436 KB Output is correct
15 Correct 1206 ms 3816 KB Output is correct
16 Correct 2751 ms 4324 KB Output is correct
17 Execution timed out 3063 ms 5996 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2668 KB Output is correct
2 Correct 4 ms 2668 KB Output is correct
3 Correct 5 ms 2796 KB Output is correct
4 Correct 5 ms 2796 KB Output is correct
5 Correct 5 ms 2796 KB Output is correct
6 Correct 5 ms 2796 KB Output is correct
7 Correct 7 ms 2796 KB Output is correct
8 Correct 4 ms 2796 KB Output is correct
9 Correct 5 ms 2796 KB Output is correct
10 Correct 5 ms 2796 KB Output is correct
11 Correct 5 ms 2796 KB Output is correct
12 Correct 5 ms 2796 KB Output is correct
13 Correct 5 ms 2796 KB Output is correct
14 Correct 282 ms 3436 KB Output is correct
15 Correct 1206 ms 3816 KB Output is correct
16 Correct 2751 ms 4324 KB Output is correct
17 Execution timed out 3063 ms 5996 KB Time limit exceeded
18 Halted 0 ms 0 KB -