#include <bits/stdc++.h>
/*
To get a certain card value, min/max operations must be done to the cost
Only dependent on lower/equal/greater than correct value
In the end, cost and value must be combined in the same part
(1 1) iff both have max 1
(-1 -1) iff both have max -1
Do not create (-1 1) - cannot do anything about it after (0 0)
(1 0) and (0 -1) - must have a (1 -1) or (-1 1) (anywhere)
(1 0) needs (-1 1), (0 -1) needs (1 -1)
Then min/max
If >3 (1 -1)s, always possible
If (0 0), left/right cannot all be (1 -1) or (-1 1)
If (1 0) (0 -1) (both decreasing), there must be dec in middle/left, or inc in middle/right (cannot be)
If (1 0) (0 1),
----+- -> - only
2 + -> can do +
-----+ -> can do +
Can do + if end in + or at least 2 +
If middle has both - and +, def possible
Through max/min, differences always decrease
They can both be - and + and doesn't matter, or -++++++-
*/
int main(){
int n,q;
std::cin>>n>>q;
std::vector<std::pair<int,int>> nums;
for(int i=0;i<n;i++){
int a,b;
std::cin>>a>>b;
nums.push_back({a,b});
}
for(int i=0;i<q;i++){
int a,b;
std::cin>>a>>b;
std::vector<int> nnums;
std::vector<int> nprefs,nsuffs(n);
std::set<int> nminus,nplus;
std::vector<int> nwzp,nwzn,nwz;
int neuleft=3;//3 for neu only, -2 for neg, -1 for neg/neu, 0 for all
for(int j=0;j<n;j++){
if(nums[j].first<a&&nums[j].second>b){
if(j==0)neuleft=2;
else neuleft=std::min(0,neuleft+1);
nnums.push_back(1);
nplus.insert(j);
}
if(nums[j].first<a&&nums[j].second==b||nums[j].first==a&&nums[j].second>b){
nnums.push_back(2);
neuleft=std::min(0,neuleft+1);
nplus.insert(j);
nwzp.push_back(j);
}
if(nums[j].first<a&&nums[j].second<b||nums[j].first>a&&nums[j].second>b){
if(neuleft==-2)neuleft=-1;
if(neuleft==2)neuleft=1;
nnums.push_back(0);
}
if(nums[j].first>a&&nums[j].second==b||nums[j].first==a&&nums[j].second<b){
nnums.push_back(-2);
neuleft=std::max(0,neuleft-1);
nminus.insert(j);
nwzn.push_back(j);
}
if(nums[j].first>a&&nums[j].second<b){
if(j==0)neuleft=-2;
else neuleft=std::max(0,neuleft-1);
nnums.push_back(-1);
nminus.insert(j);
}
if(nums[j].first==a&&nums[j].second==b){
nnums.push_back(0);
nwz.push_back(j);
}
nprefs.push_back(neuleft);
}
int neuright=3;
for(int j=n;j--;){
if(nnums[j]==1){
if(j==0)neuright=2;
else neuright=std::min(0,neuright+1);
}
if(nnums[j]==2)neuright=std::min(0,neuright+1);
if(nnums[j]==0){
if(neuright==-2)neuright=-1;
if(neuright==2)neuright=1;
}
if(nnums[j]==-1){
if(j==0)neuright=-2;
else neuright=std::max(0,neuright-1);
}
if(nnums[j]==-2)neuright=std::max(0,neuright-1);
nsuffs[j]=neuright;
}
bool can=false;
if(!nwzp.empty()&&!nwzn.empty()){
auto lnb=nminus.upper_bound(nwzp[0]);
auto lpb=nplus.lower_bound(nwzn.back());
if(lpb!=nplus.begin()&&lnb!=nminus.end()){
can=true;
}
lnb=nminus.upper_bound(nwzn[0]);
lpb=nplus.lower_bound(nwzp.back());
if(lpb!=nplus.begin()&&lnb!=nminus.end()){
can=true;
}
}
if(!nwz.empty()){
int pr1=nprefs[nwz[0]];
int pr2=nsuffs[nwz[0]];
if(pr1!=2&&pr1!=-2&&pr2!=2&&pr2!=-2){
can=true;
}
}
if(!can){
int cni=0;
for(int j=0;j<nwzp.size();j++){
while(cni<nwzn.size()&&nwzn[cni]<nwzp[j])cni++;
if(cni>=nwzn.size())break;
if(nprefs[nwzp[j]]*nsuffs[nwzn[cni]]<=0){
can=true;
break;
}
}
cni=0;
for(int j=0;j<nwzn.size();j++){
while(cni<nwzp.size()&&nwzp[cni]<nwzn[j])cni++;
if(cni>=nwzp.size())break;
if(nprefs[nwzn[j]]*nsuffs[nwzp[cni]]<=0){
can=true;
break;
}
}
}
if(can)std::cout<<i+1<<' ';
}
std::cout<<'\n';
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:59:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
59 | if(nums[j].first<a&&nums[j].second==b||nums[j].first==a&&nums[j].second>b){
Main.cpp:65:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
65 | if(nums[j].first<a&&nums[j].second<b||nums[j].first>a&&nums[j].second>b){
Main.cpp:71:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
71 | if(nums[j].first>a&&nums[j].second==b||nums[j].first==a&&nums[j].second<b){
Main.cpp:129:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for(int j=0;j<nwzp.size();j++){
| ~^~~~~~~~~~~~
Main.cpp:130:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | while(cni<nwzn.size()&&nwzn[cni]<nwzp[j])cni++;
| ~~~^~~~~~~~~~~~
Main.cpp:131:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | if(cni>=nwzn.size())break;
| ~~~^~~~~~~~~~~~~
Main.cpp:138:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for(int j=0;j<nwzn.size();j++){
| ~^~~~~~~~~~~~
Main.cpp:140:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | while(cni<nwzp.size()&&nwzp[cni]<nwzn[j])cni++;
| ~~~^~~~~~~~~~~~
Main.cpp:141:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | if(cni>=nwzp.size())break;
| ~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
