#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()
#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)
using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;
template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const char nl = '\n';
const int mxN = 2e5 + 10;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;
constexpr int blksz = 750;
typedef int node;
struct BIT{
//ask for queries 0 idxed or remove ++idx/++r
vector<node> bit;
int n;
void init(int x){
n=x+1;
bit.assign(n + 1,0);
}
node sum(int r){
node ret = 0;
for(r++; r ; r -= r & -r){
ret += bit[r];
}
return ret;
}
node sum(int l, int r){
return sum(r) - sum(l-1);
}
void add(int idx, node delta){
for(idx++; idx < n; idx += idx & -idx){
bit[idx] += delta;
}
}
};
struct T{
int a, b, c, blk, q;
bool operator<(const T& x) const{
return blk == x.blk ? a < x.a : blk < x.blk;
};
};
int n, q, aptr = -1, bptr = -1; vector<int> amt, ans, vals; vector<T> Q; vector<T> proc; set<int> A, B, C;
vector<vector<int>> as, bs; BIT bit; vector<int> chk;
map<int, int> compress(set<int> x){
map<int, int> res;
int ctr = 0;
trav(y, x){
res[y] = ctr;
ctr++;
}
return res;
}
void upd(int pos, int dif, vector<vector<int>>&cur){
trav(x, cur[pos]){
int old = vals[x];
vals[x]+=dif;
if(old == 1 && vals[x] == 2) bit.add(x, 1);
else if(old == 2 && vals[x] == 1) bit.add(x, -1);
}
}
void mo(int& ptr, int x, vector<vector<int>>& cur){
while(ptr > x){
ptr--;
upd(ptr, 1, cur);
}
while(ptr < x){
upd(ptr, -1, cur);
ptr++;
}
}
int32_t main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> q;
aptr = n+q; bptr = n+q;
proc.resize(n);
as.resize(n+q); bs.resize(n+q);
bit.init(n+q);
F0R(i, n){
cin >> proc[i].a >> proc[i].b; proc[i].c = proc[i].b + proc[i].a;
A.insert(proc[i].a);
B.insert(proc[i].b);
C.insert(proc[i].c);
}
Q.resize(q);
vals.resize(q+n);
F0R(i, q){
cin >> Q[i].a >> Q[i].b >> Q[i].c;
A.insert(Q[i].a);
B.insert(Q[i].b);
C.insert(Q[i].c);
}
map<int, int> acom = compress(A);
map<int, int> bcom = compress(B);
map<int, int> ccom = compress(C);
F0R(i, n){
proc[i].a = acom[proc[i].a];
proc[i].b = bcom[proc[i].b];
proc[i].c = ccom[proc[i].c];
// cout << proc[i].a << " " << proc[i].b << " " << proc[i].c << endl;
}
sort(all(proc), [](T ax, T bx){
return ax.c < bx.c;
});
// F0R(i, n){
// cout << proc[i].a << " " << proc[i].b << " " << proc[i].c << endl;
// }
chk.resize(n+q, 1<<30);
// cout << "lol" << endl;
F0R(i, n){
as[proc[i].a].pb(i);
bs[proc[i].b].pb(i);
ckmin(chk[proc[i].c], i);
}
R0F(i, n+q-1){
ckmin(chk[i], chk[i+1]);
}
// F0R(i, n){
// cout << chk[i] << endl;
// }
// cout << "lol" << endl;
F0R(i, q){
Q[i].a = acom[Q[i].a];
Q[i].b = bcom[Q[i].b];
Q[i].c = ccom[Q[i].c];
Q[i].blk = Q[i].b/blksz;
Q[i].q = i;
}
sort(all(Q));
ans.resize(q);
F0R(i, q){
T& cur = Q[i];
mo(bptr, cur.b, bs);
mo(aptr, cur.a, as);
ans[cur.q] = bit.sum(chk[cur.c], n+q-1);
}
F0R(i, q){
cout << ans[i] << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3076 ms |
46120 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3076 ms |
46120 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
