#include<bits/stdc++.h>
//#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define INF 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define all(a) a.begin(),a.end()
#define pi 3.14159265359
#define TASKNAME "examination"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef pair<ii,ii> iv;
const int MAXN = 120005;
const int block = 316;
const int MAXBLOCK = 320;
int n,q,x,start,b,RealIndex,res=0;
iv score[MAXN], original[MAXN];
int BIT[330][5*MAXN],prep[MAXN],rev[MAXN],cnt[MAXN],answer[MAXN],complexity;
vector<int> listval;
vector<iv> query;
void upd(int block,int id,int x){
for(int i=id;i>0;i-=i&(-i)){
BIT[block][i] += x;
}
}
int get(int block,int id){
res = 0;
for(int i=id;i<=listval.size();i+=i&(-i)){
res += BIT[block][i];
}
return res;
}
int bs(int l,int r,int x){
res = r+1;
while(l<=r){
int mid = (l+r)>>1;
if (original[mid].se.fi >= x){
res = mid;
r = mid - 1;
}
else l = mid + 1;
}
return res;
}
void fastscan(int &number)
{
//variable to indicate sign of input number
bool negative = false;
register int c;
number = 0;
// extract current character from buffer
c = getchar();
if (c=='-')
{
// number is negative
negative = true;
// extract the next character from the buffer
c = getchar();
}
// Keep on extracting characters if they are integers
// i.e ASCII Value lies from '0'(48) to '9' (57)
for (; (c>47 && c<58); c=getchar())
number = number *10 + c - 48;
// if scanned input has a negative sign, negate the
// value of the input number
if (negative)
number *= -1;
}
main()
{
fast;
if (fopen(TASKNAME".inp","r")){
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".out","w",stdout);
}
fastscan(n);
fastscan(q);
for(int i=1;i<=n;i++){
// cin>>score[i].se.fi>>score[i].se.se;
fastscan(score[i].se.fi);
fastscan(score[i].se.se);
score[i].fi.se = score[i].se.fi + score[i].se.se;
listval.pb(score[i].se.fi);
listval.pb(score[i].se.se);
listval.pb(score[i].fi.se);
}
sort(score+1,score+1+n,[](const iv &a,const iv &b){
return a.se.fi < b.se.fi;
});
for(int i=1;i<=q;i++){
int x,y,z;
// cin>>x>>y>>z;
fastscan(x);
fastscan(y);
fastscan(z);
listval.pb(x);
listval.pb(y);
listval.pb(z);
query.pb({{i,x},{y,z}});
}
sort(listval.begin(),listval.end());
listval.erase(unique(listval.begin(),listval.end()),listval.end());
for(int i=1;i<=max(q,n);i++){
if (i<=n){
score[i].se.fi = lower_bound(all(listval),score[i].se.fi) - listval.begin() + 1;
score[i].se.se = lower_bound(all(listval),score[i].se.se) - listval.begin() + 1;
score[i].fi.se = lower_bound(all(listval),score[i].fi.se) - listval.begin() + 1;
}
if (i<=q){
query[i-1].se.fi = lower_bound(all(listval),query[i-1].se.fi) - listval.begin() + 1;
query[i-1].se.se = lower_bound(all(listval),query[i-1].se.se) - listval.begin() + 1;
query[i-1].fi.se = lower_bound(all(listval),query[i-1].fi.se) - listval.begin() + 1;
}
}
for(int i=1;i<=n;i++){
score[i].fi.fi = i;
original[i] = score[i];
}
sort(query.begin(),query.end(),[](const iv &a,const iv &b){
return a.se.se > b.se.se;
});
sort(score+1,score+1+n,[](const iv &a,const iv &b){
return a.fi.se > b.fi.se;
});
for(int i=1;i<=n;i++){
prep[i] = i / block;
}
int ptr = 1;
for(int i=0;i<query.size();i++){
while(ptr <= n and score[ptr].fi.se >= query[i].se.se){
RealIndex = score[ptr].fi.fi;
rev[RealIndex]++;
b = prep[RealIndex];
cnt[b]++;
upd(b,score[ptr].se.se,1);
ptr++;
}
start = bs(1,n,query[i].fi.se);
b = prep[start];
for(int j=start;j<=n;j++){
if (original[j].se.fi >= query[i].fi.se and
original[j].se.se >= query[i].se.fi and
original[j].fi.se >= query[i].se.se and
rev[j] > 0){
answer[query[i].fi.fi]++;
}
complexity++;
if (prep[j] != prep[j+1]) {
break;
}
}
for(int cur=b+1;cur<MAXBLOCK;cur++){
if (cur * block > n) break;
if (cnt[cur] == 0) continue;
complexity++;
answer[query[i].fi.fi] += get(cur,query[i].se.fi);
}
}
for(int i=1;i<=q;i++){
cout<<answer[i]<<endl;
}
}
Compilation message
examination.cpp: In function 'int get(int, int)':
examination.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(int i=id;i<=listval.size();i+=i&(-i)){
| ~^~~~~~~~~~~~~~~~
examination.cpp: In function 'void fastscan(int&)':
examination.cpp:59:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
59 | register int c;
| ^
examination.cpp: At global scope:
examination.cpp:85:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
85 | main()
| ^~~~
examination.cpp: In function 'int main()':
examination.cpp:146:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | for(int i=0;i<query.size();i++){
| ~^~~~~~~~~~~~~
examination.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
89 | freopen(TASKNAME".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
90 | freopen(TASKNAME".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 6 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 7 |
Incorrect |
10 ms |
27228 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1987 ms |
226140 KB |
Output is correct |
| 2 |
Correct |
1922 ms |
226744 KB |
Output is correct |
| 3 |
Correct |
1785 ms |
355836 KB |
Output is correct |
| 4 |
Correct |
648 ms |
326604 KB |
Output is correct |
| 5 |
Correct |
1659 ms |
412988 KB |
Output is correct |
| 6 |
Correct |
225 ms |
358716 KB |
Output is correct |
| 7 |
Execution timed out |
3027 ms |
419184 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1987 ms |
226140 KB |
Output is correct |
| 2 |
Correct |
1922 ms |
226744 KB |
Output is correct |
| 3 |
Correct |
1785 ms |
355836 KB |
Output is correct |
| 4 |
Correct |
648 ms |
326604 KB |
Output is correct |
| 5 |
Correct |
1659 ms |
412988 KB |
Output is correct |
| 6 |
Correct |
225 ms |
358716 KB |
Output is correct |
| 7 |
Execution timed out |
3027 ms |
419184 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 6 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 7 |
Incorrect |
10 ms |
27228 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
