Submission #1071533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071533		phong	Examination (JOI19_examination)	C++17	100 / 100	417 ms	127892 KiB

examination

#include<bits/stdc++.h>

#define ll long long
const int nmax = 6e5 + 5, N = 1e5;
const ll oo = 1e18 + 1, base = 311;
const int lg = 19, M = 10;
const ll mod = 998244353, mod2 = 1e9 + 5277;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;

int n, q;
struct node{
    int x, y, z;
}a[nmax];
vector<pii> tree[nmax << 2];



void build(int id, int l, int r){
    if(l == r){
        tree[id].push_back({a[l].y, a[l].z});
        return;
    }
    int mid = r + l >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    tree[id].resize(r - l + 1);
    merge(tree[id << 1].begin(), tree[id << 1].end(), tree[id << 1 | 1].begin(), tree[id << 1 | 1].end(), tree[id].begin());
}
vector<node> Q[nmax];

void update(int id, int l, int r, int u, int v, int B, int C, int idx){
    if(l > v || r < u) return;
    if(l >= u && r <= v){
        Q[id].push_back({B, C, idx});
        return;
    }
    int mid = r + l>> 1;
    update(id << 1, l, mid, u, v, B, C, idx);
    update(id << 1 | 1, mid + 1, r, u, v, B, C, idx);
}
struct Fen{
    int f[nmax];
    vector<int> tmp;
    void update(int u, int val){
        for(; u ; u -= u &-u) f[u] += val, tmp.push_back(u);
    }
    int get(int u){
        int res = 0;
        for(; u <= 6 * n; u += u&-u) res += f[u];
        return res;
    }
    void clear(){
        for(auto p : tmp){
            f[p] = 0;
        }
        tmp.clear();
    }
}F;
int ans[nmax];
void apply(int id, int l, int r){
    sort(Q[id].begin(), Q[id].end(), [](node a, node b){
        return a.x > b.x;
         });
    int pos = tree[id].size() - 1;
    for(auto [B, C, idx] : Q[id]){
        while(pos >= 0 && tree[id][pos].fi >= B){
            F.update(tree[id][pos].se, 1);
            --pos;
        }
        ans[idx] += F.get(C);
    }
    F.clear();
    if(l != r){
        int mid = r+ l >> 1;
        apply(id << 1, l, mid);
        apply(id << 1 | 1, mid + 1, r);
    }
}
node b[nmax];

main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n >> q;
    vector<int> nen;
    for(int i = 1; i <= n; ++i){
        cin >> a[i].x >> a[i].y;
        a[i].z = a[i].x + a[i].y;
        nen.push_back(a[i].x);
        nen.push_back(a[i].y);
        nen.push_back(a[i].z);
    }
    for(int e = 1; e<= q; ++e){
        cin >> b[e].x >> b[e].y>>b[e].z;
        nen.push_back(b[e].x);
        nen.push_back(b[e].y);
        nen.push_back(b[e].z);
    }
    sort(nen.begin(), nen.end());
    nen.erase(unique(nen.begin(), nen.end()), nen.end());
    for(int i = 1; i <= n; ++i){
        a[i].x = lower_bound(nen.begin(), nen.end(), a[i].x) - nen.begin() + 1;
        a[i].y = lower_bound(nen.begin(), nen.end(), a[i].y) - nen.begin() + 1;
        a[i].z = lower_bound(nen.begin(), nen.end(), a[i].z) - nen.begin() + 1;
    }

    sort(a + 1, a + 1 + n, [](node a, node b){
         return a.x < b.x;
         });
    build(1, 1, n);
    for(int e = 1; e <= q; ++e){
        int A, B,C;
        A = lower_bound(nen.begin(), nen.end(), b[e].x) - nen.begin() + 1;
        B = lower_bound(nen.begin(), nen.end(), b[e].y) - nen.begin() + 1;
        C = lower_bound(nen.begin(), nen.end(), b[e].z) - nen.begin() + 1;
        int l = 1 , r = n, kq = n + 1;
        while(l <= r){
            int mid = r + l >> 1;
            if(a[mid].x >= A){
                r = mid - 1;
                kq = mid;
            }
            else l = mid + 1;
        }
//        cout <<kq << ' ';
        update(1, 1, n, kq, n, B, C, e);
    }
    apply(1, 1, n);
    for(int i = 1; i <= q; ++i) cout << ans[i] << endl;

}
/*




*/

Compilation message (stderr)

examination.cpp: In function 'void build(int, int, int)':
examination.cpp:28:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |     int mid = r + l >> 1;
      |               ~~^~~
examination.cpp: In function 'void update(int, int, int, int, int, int, int, int)':
examination.cpp:42:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |     int mid = r + l>> 1;
      |               ~~^~~
examination.cpp: In function 'void apply(int, int, int)':
examination.cpp:79:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |         int mid = r+ l >> 1;
      |                   ~^~~
examination.cpp: At global scope:
examination.cpp:86:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   86 | main(){
      | ^~~~
examination.cpp: In function 'int main()':
examination.cpp:125:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  125 |             int mid = r + l >> 1;
      |                       ~~^~~

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