oj.uz

Submission #338701

# Submission time Handle Problem Language Result Execution time Memory
338701 2020-12-23T17:12:02 Z Thistle Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 874 ms 69804 KB 
#pragma GCC target ("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<unordered_map>
#include<climits>
#include<fstream>
#include<complex>
#include<time.h>
#include<cassert>
#include<functional>
#include<numeric>
#include<tuple>
using namespace std;
using ll = long long;
using ld = long double;
using H = pair<ll, ll>;
using P = pair<ll, H>;
using vi = vector<ll>;
#define all(a) (a).begin(),(a).end()
#define fs first
#define sc second
#define xx first
#define yy second.first
#define zz second.second
#define Q(i,j,k) mkp(i,mkp(j,k))
#define rng(i,s,n) for(ll i = (s) ; i < (n) ; i++)
#define rep(i,n) rng(i, 0, (n))
#define mkp make_pair
#define vec vector
#define pb emplace_back
#define siz(a) (int)(a).size()
#define crdcomp(b) sort(all((b)));(b).erase(unique(all((b))),(b).end())
#define getidx(b,i) (lower_bound(all(b),(i))-(b).begin())
#define ssp(i,n) (i==(ll)(n)-1?"\n":" ")
#define ctoi(c) (int)(c-'0')
#define itoc(c) (char)(c+'0')
#define cyes printf("Yes\n")
#define cno printf("No\n")
#define cdf(n) for(int quetimes_=(n);quetimes_>0;quetimes_--)
#define gcj printf("Case #%lld: ",qq123_+1)
#define readv(a,n) a.resize(n,0);rep(i,(n)) a[i]=read()
#define found(a,x) (a.root(x)!=a.end())
constexpr ll mod = (ll)1e9 + 7;
constexpr ll Mod = 998244353;
constexpr ld EPS = 1e-10;
constexpr ll inf = (ll)3 * 1e18;
constexpr int Inf = (ll)15 * 1e8;
constexpr int dx[] = { -1,1,0,0 }, dy[] = { 0,0,-1,1 };
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
ll read() { ll u, k = scanf("%lld", &u); return u; }
string reads() { string s; cin >> s; return s; }
H readh(short g = 0) { H u; int k = scanf("%lld %lld", &u.fs, &u.sc); if (g == 1) u.fs--, u.sc--; if (g == 2) u.fs--; return u; }
bool ina(H t, int h, int w) { return 0 <= t.fs && t.fs < h && 0 <= t.sc && t.sc < w; }
bool ina(int t, int l, int r) { return l <= t && t < r; }
ll gcd(ll i, ll j) { return j ? gcd(j, i % j) : i; }
ll ppc(ll x) {
    int sum = 0; for (int i = 0; i < 60; i++)if ((1ll << i) & x) sum++;
    return sum;
}
void fin1() { printf("-1\n"); exit(0); }
void fin0() { printf("0\n"); exit(0); }

template<typename T>
class csum {
    vec<T> v;
public:
    csum(vec<T>& a) :v(a) { build(); }
    csum() {}
    csum(int sz) { init(sz); }
    void init(int sz) { v = vector<T>(sz, 0); }
    void init(vec<T>& a) { v = a; build(); }
    void build() {
        for (int i = 1; i < v.size(); i++) v[i] += v[i - 1];
    }
    void add(int l, int r, T x) {
        v[l] += x;
        v[r] -= x;
    }//[l,r)
    //[l,r]
    T a(int l, int r) {
        if (r < l) return 0;
        return v[r] - (l == 0 ? 0 : v[l - 1]);
    }
    //[l,r)
    T b(int l, int r) {
        return a(l, r - 1);
    }
    T a(pair<int, int>t) {
        return a(t.first, t.second);
    }
    T b(pair<int, int>t) {
        return b(t.first, t.second);
    }
    T operator[](int x)const {
        return v[x];
    }
};
template<ll mod>
class modint {
public:ll v;
      modint(ll v = 0) { s(v % mod + mod); }
      constexpr static int fn_ = (ll)2e6 + 5;
      static vector<modint>fact, comp;
      modint pow(ll x) const {
          modint b(v), c(1);
          while (x) {
              if (x & 1) c *= b;
              b *= b;
              x >>= 1;
          }
          return c;
      }
      inline modint& s(int vv) {
          v = vv < mod ? vv : vv - mod;
          return *this;
      }
      inline modint inv()const { return pow(mod - 2); }
      inline modint operator-()const { return modint() - *this; }
      inline modint& operator+=(const modint b) { return s(v + b.v); }
      inline modint& operator-=(const modint b) { return s(v + mod - b.v); }
      inline modint& operator*=(const modint b) { v = v * b.v % mod; return *this; }
      inline modint& operator/=(const modint b) { v = v * b.inv().v % mod; return *this; }
      inline modint operator+(const modint& b) const { return modint(v) += b; }
      inline modint operator-(const modint& b) const { return modint(v) -= b; }
      inline modint operator*(const modint& b) const { return modint(v) *= b; }
      inline modint operator/(const modint& b) const { return modint(v) /= b; }
      friend ostream& operator<<(ostream& os, const modint& m) {
          return os << m.v;
      }
      friend istream& operator>>(istream& is, modint& m) {
          int x; is >> x; m = modint(x);
          return is;
      }
      bool operator<(const modint& r)const { return v < r.v; }
      bool operator>(const modint& r)const { return v > r.v; }
      bool operator<=(const modint& r)const { return v <= r.v; }
      bool operator>=(const modint& r)const { return v >= r.v; }
      bool operator==(const modint& r)const { return v == r.v; }
      bool operator!=(const modint& r)const { return v != r.v; }
      explicit operator bool()const { return v; }
      explicit operator int()const { return v; }
      modint comb(modint k) {
          if (k > *this) return modint();
          if (fact.empty()) combinit();
          if (v >= fn_) {
              if (k > *this - k) k = *this - k;
              modint tmp(1);
              for (int i = v; i >= v - k.v + 1; i--) tmp *= modint(i);
              return tmp * comp[k.v];
          }
          return fact[v] * comp[k.v] * comp[v - k.v];
      }//nCk
      modint perm(modint k) {
          if (k > *this) return modint();
          if (fact.empty()) combinit();
          if (v >= fn_) {
              modint tmp(1);
              for (int i = v; i >= v - k.v + 1; i--) tmp *= modint(i);
              return tmp;
          }
          return fact[v] * comp[v - k.v];
      }//nPk
      static void combinit() {
          fact.assign(fn_, modint());
          fact[0] = 1;
          for (int i = 1; i < fn_; i++) fact[i] = fact[i - 1] * modint(i);
          comp.assign(fn_, modint());
          comp[fn_ - 1] = fact[fn_ - 1].inv();
          for (int i = fn_ - 2; i >= 0; i--) comp[i] = comp[i + 1] * modint(i + 1);
      }
};
using mint = modint<ll(1e9 + 7)>; template<>vec<mint> mint::fact = vec<mint>(); template<>vec<mint> mint::comp = vec<mint>();
//--------------------------------------------------------------
//--------------------------------------------------------------
int n, m, rr = 1;
vi dat[800000];
//a以上b未満の値が初めて出てくるindexを返す 出てこないならm
int lb(int i, int a, int b, int l, int r) {
    if (lower_bound(all(dat[i]), b) - lower_bound(all(dat[i]), a) == 0) {
        return m;
    }
    if (r - l == 1) return l;
    int k = lb(i * 2, a, b, l, (l + r) / 2);
    if (k < m) return k;
    return lb(i * 2 + 1, a, b, (l + r) / 2, r);
}
int query(int i, int a, int b, int x, int l, int r) {
    if (b <= l || r <= a) return 0;
    if (a <= l && r <= b) {
        return siz(dat[i]) - (lower_bound(all(dat[i]), x) - dat[i].begin());
    }
    return query(i * 2, a, b, x, l, (l + r) / 2) + query(i * 2 + 1, a, b, x, (l + r) / 2, r);
}//a以上b未満の区間に、x以上の値は何個あるか？
signed main() {
    cin >> n >> m;
    vec<H>a; vi b;
    rep(i, n) a.pb(readh());
    readv(b, m);
    reverse(all(b));
    while (rr < m) rr *= 2;
    rng(i, rr, rr + m) dat[i].pb(b[i - rr]);
    for (int i = rr - 1; i >= 1; i--) {
        merge(all(dat[i * 2]), all(dat[i * 2 + 1]), back_inserter(dat[i]));
    }
    ll ans = 0;
    rep(i, n) {
        int k = lb(1, min(a[i].fs, a[i].sc), max(a[i].fs, a[i].sc), 0, rr);
        int num = query(1, 0, k, max(a[i].fs, a[i].sc), 0, rr);
        if (k == m) {
            if (num % 2 == 0) ans += a[i].fs;
            else ans += a[i].sc;
        }
        else {
            if (a[i].fs > a[i].sc) swap(a[i].fs, a[i].sc);
            //a[i].fsがひっくり返されたのがk
            //現在の表はa[i].sc
            if (num % 2 == 0) ans += a[i].sc;
            else ans += a[i].fs;
        }
    }
    cout << ans << endl;
}

Compilation message

fortune_telling2.cpp: In function 'll read()':
fortune_telling2.cpp:69:19: warning: unused variable 'k' [-Wunused-variable]
   69 | ll read() { ll u, k = scanf("%lld", &u); return u; }
      |                   ^
fortune_telling2.cpp: In function 'H readh(short int)':
fortune_telling2.cpp:71:33: warning: unused variable 'k' [-Wunused-variable]
   71 | H readh(short g = 0) { H u; int k = scanf("%lld %lld", &u.fs, &u.sc); if (g == 1) u.fs--, u.sc--; if (g == 2) u.fs--; return u; }
      |                                 ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19308 KB Output is correct
2 Correct 14 ms 19308 KB Output is correct
3 Correct 14 ms 19308 KB Output is correct
4 Correct 15 ms 19308 KB Output is correct
5 Correct 17 ms 19432 KB Output is correct
6 Correct 14 ms 19308 KB Output is correct
7 Correct 15 ms 19308 KB Output is correct
8 Correct 15 ms 19308 KB Output is correct
9 Correct 14 ms 19308 KB Output is correct
10 Correct 14 ms 19308 KB Output is correct
11 Correct 15 ms 19456 KB Output is correct
12 Correct 15 ms 19308 KB Output is correct
13 Correct 15 ms 19308 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19308 KB Output is correct
2 Correct 14 ms 19308 KB Output is correct
3 Correct 14 ms 19308 KB Output is correct
4 Correct 15 ms 19308 KB Output is correct
5 Correct 17 ms 19432 KB Output is correct
6 Correct 14 ms 19308 KB Output is correct
7 Correct 15 ms 19308 KB Output is correct
8 Correct 15 ms 19308 KB Output is correct
9 Correct 14 ms 19308 KB Output is correct
10 Correct 14 ms 19308 KB Output is correct
11 Correct 15 ms 19456 KB Output is correct
12 Correct 15 ms 19308 KB Output is correct
13 Correct 15 ms 19308 KB Output is correct
14 Correct 42 ms 21352 KB Output is correct
15 Correct 72 ms 23908 KB Output is correct
16 Correct 99 ms 25956 KB Output is correct
17 Correct 142 ms 28640 KB Output is correct
18 Correct 141 ms 28896 KB Output is correct
19 Correct 140 ms 28768 KB Output is correct
20 Correct 148 ms 28640 KB Output is correct
21 Correct 118 ms 28640 KB Output is correct
22 Correct 78 ms 28256 KB Output is correct
23 Correct 81 ms 28128 KB Output is correct
24 Correct 84 ms 28128 KB Output is correct
25 Correct 72 ms 28256 KB Output is correct
26 Correct 127 ms 28512 KB Output is correct
27 Correct 191 ms 28716 KB Output is correct
28 Correct 124 ms 28768 KB Output is correct
29 Correct 128 ms 28640 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19308 KB Output is correct
2 Correct 14 ms 19308 KB Output is correct
3 Correct 14 ms 19308 KB Output is correct
4 Correct 15 ms 19308 KB Output is correct
5 Correct 17 ms 19432 KB Output is correct
6 Correct 14 ms 19308 KB Output is correct
7 Correct 15 ms 19308 KB Output is correct
8 Correct 15 ms 19308 KB Output is correct
9 Correct 14 ms 19308 KB Output is correct
10 Correct 14 ms 19308 KB Output is correct
11 Correct 15 ms 19456 KB Output is correct
12 Correct 15 ms 19308 KB Output is correct
13 Correct 15 ms 19308 KB Output is correct
14 Correct 42 ms 21352 KB Output is correct
15 Correct 72 ms 23908 KB Output is correct
16 Correct 99 ms 25956 KB Output is correct
17 Correct 142 ms 28640 KB Output is correct
18 Correct 141 ms 28896 KB Output is correct
19 Correct 140 ms 28768 KB Output is correct
20 Correct 148 ms 28640 KB Output is correct
21 Correct 118 ms 28640 KB Output is correct
22 Correct 78 ms 28256 KB Output is correct
23 Correct 81 ms 28128 KB Output is correct
24 Correct 84 ms 28128 KB Output is correct
25 Correct 72 ms 28256 KB Output is correct
26 Correct 127 ms 28512 KB Output is correct
27 Correct 191 ms 28716 KB Output is correct
28 Correct 124 ms 28768 KB Output is correct
29 Correct 128 ms 28640 KB Output is correct
30 Correct 159 ms 61364 KB Output is correct
31 Correct 304 ms 63584 KB Output is correct
32 Correct 475 ms 66012 KB Output is correct
33 Correct 844 ms 69804 KB Output is correct
34 Correct 123 ms 61024 KB Output is correct
35 Correct 849 ms 69460 KB Output is correct
36 Correct 832 ms 69608 KB Output is correct
37 Correct 850 ms 69588 KB Output is correct
38 Correct 811 ms 69588 KB Output is correct
39 Correct 874 ms 69484 KB Output is correct
40 Correct 606 ms 69332 KB Output is correct
41 Correct 829 ms 69460 KB Output is correct
42 Correct 844 ms 69460 KB Output is correct
43 Correct 333 ms 68948 KB Output is correct
44 Correct 328 ms 68820 KB Output is correct
45 Correct 327 ms 68692 KB Output is correct
46 Correct 393 ms 67540 KB Output is correct
47 Correct 454 ms 67412 KB Output is correct
48 Correct 838 ms 69460 KB Output is correct
49 Correct 719 ms 69716 KB Output is correct