Submission #1201874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201874		doq	Examination (JOI19_examination)	C++20	0 / 100	465 ms	25200 KiB

examination

# include <bits/stdc++.h>
using namespace std;
#define int long long
bool doq = 0;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, ll> pil;
typedef pair <ll, int> pli;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <pii> vii;

#define ld long double
#define fi first
#define se second
#define pb push_back
#define fon(i, a, b) for(int i = a, _b = b; i < _b; i++)
#define fo(i, a, b) for(int i = a, _b = b; i <= _b; i++)
#define fod(i, a, b) for(int i = a, _b = b; i >= _b; i--)
#define ALL(a) a.begin(), a.end()
#define endl "\n"
#define BIT(mask, i) ((mask >> (i)) & 1)
#define MASK(a) (1LL << a)
#define sz(A) (int)A.size()
#define uni(V) sort(ALL(V)), V.resize(unique(ALL(V)) - V.begin())
#define hal(x, y) (((x) + (y))/2)

template <class T> bool maxi(T &a, const T b){if(a < b){a = b; return true;}return false;}
template <class T> bool mini(T &a, const T b){if(a > b){a = b; return true;}return false;}

const int N = 4e5 + 7, M = 1e3 + 5, LOG = __lg(N) + 1, base = 31;
const int oo = 2e9, sm = 1e9 + 7, mod1 = 1e9 + 7, mod2 = 1e9 + 3;
const ll inf = 1e15;
const int mod = 1e9 + 7, inf_int = 1e9, B = 500;

int n, q, f[N * 3], ans[N];
vi vx;
struct pp{int x, y, sum, k, id;} a[N];
struct ph{int y, sum, k, id; };

int id(int n){
    return lower_bound(vx.begin(), vx.end(), n) - vx.begin() + 2;
}

struct BIT{
    void update(int id, int val){
        for(; id > 0; id -= id&(-id)) f[id] += val;
    }

    int get(int id){
        int res = 0;
        for(; id <= vx.size() + 3; id += id&(-id)) res += f[id];
        return res;
    }
}bit;

void nen(){
    fo(i, 1, n + q){
        vx.pb(a[i].x);vx.pb(a[i].y);vx.pb(a[i].sum);
    }
    uni(vx);
    fo(i, 1, n + q){
        a[i].x = id(a[i].x);
        a[i].y = id(a[i].y);
        a[i].sum = id(a[i].sum);
    }
}

bool cmp(pp a, pp b){
    if(a.x != b.x) return a.x > b.x;
    return a.k < b.k;
}

void init(){
    cin >> n >> q;
    fo(i, 1, n) {
        cin >> a[i].x >> a[i].y;
        a[i].sum = a[i].x + a[i].y;
        a[i].k = 1;
        a[i].id = i;
    }
    fo(i, n + 1, q + n) {
        cin >> a[i].x >> a[i].y >> a[i].sum;
        a[i].k = 0;
        a[i].id = i - n;
    }
}

bool cm(ph a, ph b){
    if(a.y != b.y) return a.y > b.y;
    return a.k < b.k;
}

void dnc(int L, int R){
    if(L == R) return;
    int m = hal(L, R);

    dnc(L, m); dnc(m+1, R);

    int l = L, r = R;

    vector<ph> q1, q2;
    fo(i, l, m) q1.pb({a[i].y, a[i].sum, a[i].k, a[i].id});
    fo(i, m+1, r) q2.pb({a[i].y, a[i].sum, a[i].k, a[i].id});

    sort(ALL(q1), cm);
    sort(ALL(q2), cm);

    vector<int> rev;
    int id = 0;
    for(ph tmp: q2){
        int y = tmp.y, type = tmp.k, sum = tmp.sum;
        while(id < q1.size() && q1[id].y >= y){
            if(q1[id].k != 0) {
                bit.update(q1[id].sum, 1);
                rev.pb(q1[id].sum);
            }
            id++;
        }
        if(type == 0)
            ans[tmp.id] += bit.get(sum);
    }

    for(int x: rev) bit.update(x, -1);
}

void pre(){
    sort(a+1, a+n+1+q, cmp);
    nen();
}

void solve(){
    dnc(1, n + q);
    fo(i, 1, q) cout << ans[i] << '\n';
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define task "1"
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }

    int tc; tc = 1;
    if(doq) cin >> tc;

    while(tc--){
        init();
        pre();
        solve();
    }

    cerr << "\nTime : " << 0.001 * clock() << "s ";
    return 0;
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:142:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
examination.cpp:143:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57