QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #499615 | #9161. Naval battle | kshitij_sodani# | 6 | 1952ms | 152392kb | C++14 | 5.6kb | 2024-07-31 16:19:53 | 2024-07-31 16:19:53 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#define endl '\n'
int aa[200001];
int bb[200001];
char tt[200001];
map<pair<int,int>,int> ss;
set<pair<int,pair<int,int>>> mi;
set<pair<int,int>> zz[1200001];
void consider(int ind, int i, char prev,char next,int dif=2){
auto j=zz[ind].lower_bound({aa[i],i+1});
pair<int,int> ll={-1,-1};
pair<int,int> rr={-1,-1};
if(j!=zz[ind].end()){
rr=(*j);
}
if(j!=zz[ind].begin()){
j--;
ll=(*j);
}
zz[ind].insert({aa[i],i});
/*if(rr.b>=0){
cout<<rr.a<<",,,"<<rr.b<<endl;
}*/
if(ll.b>=0 and rr.b>=0 and tt[ll.b]==prev and tt[rr.b]==next){
mi.erase({(aa[rr.b]-aa[rr.b])*dif,{ll.b,rr.b}});
}
if(ll.b>=0 and tt[ll.b]==prev and tt[i]==next){
mi.insert({(aa[i]-aa[ll.b])*dif,{ll.b,i}});
}
if(rr.b>=0 and tt[i]==prev and tt[rr.b]==next){
mi.insert({(aa[rr.b]-aa[i])*dif,{i,rr.b}});
}
}
void consider2(int ind, int i, char prev,char next,int dif=2){
zz[ind].erase({aa[i],i});
auto j=zz[ind].lower_bound({aa[i],i+1});
pair<int,int> ll={-1,-1};
pair<int,int> rr={-1,-1};
if(j!=zz[ind].end()){
rr=(*j);
}
if(j!=zz[ind].begin()){
j--;
ll=(*j);
}
/*if(rr.b>=0){
cout<<rr.a<<",,,"<<rr.b<<endl;
}*/
if(ll.b>=0 and rr.b>=0 and tt[ll.b]==prev and tt[rr.b]==next){
mi.insert({(aa[rr.b]-aa[rr.b])*dif,{ll.b,rr.b}});
}
if(ll.b>=0 and tt[ll.b]==prev and tt[i]==next){
mi.erase({(aa[i]-aa[ll.b])*dif,{ll.b,i}});
}
if(rr.b>=0 and tt[i]==prev and tt[rr.b]==next){
mi.erase({(aa[rr.b]-aa[i])*dif,{i,rr.b}});
}
}
void add(int i){
if(tt[i]=='N' or tt[i]=='S'){
int ind=ss[{aa[i],2}];
auto j=zz[ind].lower_bound({bb[i],i+1});
pair<int,int> ll={-1,-1};
pair<int,int> rr={-1,-1};
if(j!=zz[ind].end()){
rr=(*j);
}
if(j!=zz[ind].begin()){
j--;
ll=(*j);
}
zz[ind].insert({bb[i],i});
if(ll.b>=0 and rr.b>=0 and tt[ll.b]=='S' and tt[rr.b]=='N'){
mi.erase({bb[rr.b]-bb[rr.b],{ll.b,rr.b}});
}
if(ll.b>=0 and tt[ll.b]=='S' and tt[i]=='N'){
mi.insert({bb[i]-bb[ll.b],{ll.b,i}});
}
if(rr.b>=0 and tt[i]=='S' and tt[rr.b]=='N'){
mi.insert({bb[rr.b]-bb[i],{i,rr.b}});
}
}
else{
int ind=ss[{aa[i],3}];
auto j=zz[ind].lower_bound({aa[i],i+1});
pair<int,int> ll={-1,-1};
pair<int,int> rr={-1,-1};
if(j!=zz[ind].end()){
rr=(*j);
}
if(j!=zz[ind].begin()){
j--;
ll=(*j);
}
zz[ind].insert({aa[i],i});
if(ll.b>=0 and rr.b>=0 and tt[ll.b]=='E' and tt[rr.b]=='W'){
mi.erase({aa[rr.b]-aa[rr.b],{ll.b,rr.b}});
}
if(ll.b>=0 and tt[ll.b]=='E' and tt[i]=='W'){
mi.insert({aa[i]-aa[ll.b],{ll.b,i}});
}
if(rr.b>=0 and tt[i]=='E' and tt[rr.b]=='W'){
mi.insert({aa[rr.b]-aa[i],{i,rr.b}});
}
}
if(tt[i]=='S' or tt[i]=='W'){
int ind=ss[{aa[i]-bb[i],4}];
consider(ind,i,'S','W',2);
}
else{
int ind=ss[{aa[i]-bb[i],5}];
consider(ind,i,'E','N',2);
}
if(tt[i]=='S' or tt[i]=='E'){
int ind=ss[{aa[i]+bb[i],0}];
//cout<<ind<<":::"<<endl;
consider(ind,i,'E','S',2);
}
else{
int ind=ss[{aa[i]+bb[i],1}];
consider(ind,i,'N','W',2);
}
}
void remove(int i){
if(tt[i]=='N' or tt[i]=='S'){
int ind=ss[{aa[i],2}];
zz[ind].erase({bb[i],i});
auto j=zz[ind].lower_bound({bb[i],i+1});
pair<int,int> ll={-1,-1};
pair<int,int> rr={-1,-1};
if(j!=zz[ind].end()){
rr=(*j);
}
if(j!=zz[ind].begin()){
j--;
ll=(*j);
}
if(ll.b>=0 and rr.b>=0 and tt[ll.b]=='S' and tt[rr.b]=='N'){
mi.insert({bb[rr.b]-bb[rr.b],{ll.b,rr.b}});
}
if(ll.b>=0 and tt[ll.b]=='S' and tt[i]=='N'){
mi.erase({bb[i]-bb[ll.b],{ll.b,i}});
}
if(rr.b>=0 and tt[i]=='S' and tt[rr.b]=='N'){
mi.erase({bb[rr.b]-bb[i],{i,rr.b}});
}
}
else{
int ind=ss[{aa[i],3}];
zz[ind].erase({aa[i],i});
auto j=zz[ind].lower_bound({aa[i],i+1});
pair<int,int> ll={-1,-1};
pair<int,int> rr={-1,-1};
if(j!=zz[ind].end()){
rr=(*j);
}
if(j!=zz[ind].begin()){
j--;
ll=(*j);
}
if(ll.b>=0 and rr.b>=0 and tt[ll.b]=='E' and tt[rr.b]=='W'){
mi.insert({aa[rr.b]-aa[rr.b],{ll.b,rr.b}});
}
if(ll.b>=0 and tt[ll.b]=='E' and tt[i]=='W'){
mi.erase({aa[i]-aa[ll.b],{ll.b,i}});
}
if(rr.b>=0 and tt[i]=='E' and tt[rr.b]=='W'){
mi.erase({aa[rr.b]-aa[i],{i,rr.b}});
}
}
if(tt[i]=='S' or tt[i]=='W'){
int ind=ss[{aa[i]-bb[i],4}];
consider2(ind,i,'S','W',2);
}
else{
int ind=ss[{aa[i]-bb[i],5}];
consider2(ind,i,'E','N',2);
}
if(tt[i]=='S' or tt[i]=='E'){
int ind=ss[{aa[i]+bb[i],0}];
//cout<<ind<<":::"<<endl;
consider2(ind,i,'E','S',2);
}
else{
int ind=ss[{aa[i]+bb[i],1}];
consider2(ind,i,'N','W',2);
}
}
bool vis[200001];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin>>n;
for(int i=0;i<n;i++){
char s;
cin>>aa[i]>>bb[i]>>tt[i];
ss[{aa[i]+bb[i],0}]++;
ss[{aa[i]+bb[i],1}]++;
ss[{aa[i]-bb[i],4}]++;
ss[{aa[i]-bb[i],5}]++;
ss[{aa[i],2}]++;
ss[{bb[i],3}]++;
}
int ind=0;
for(auto j:ss){
ss[j.a]=ind;
ind++;
}
for(int i=0;i<n;i++){
add(i);
}
while(mi.size()){
int no=(*mi.begin()).a;
set<int> xx;
while(mi.size()){
pair<int,pair<int,int>> x=(*mi.begin());
if(x.a==no){
mi.erase(x);
xx.insert(x.b.a);
xx.insert(x.b.b);
}
else{
break;
}
}
for(auto j:xx){
remove(j);
vis[j]=1;
}
}
for(int i=0;i<n;i++){
if(vis[i]==0){
cout<<i+1<<endl;
}
}
/*cout<<endl;
for(auto j:mi){
cout<<j.a<<" "<<j.b.a<<":"<<j.b.b<<endl;
}
*/
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 6
Accepted
Test #1:
score: 6
Accepted
time: 3ms
memory: 60632kb
input:
2 675333810 792019962 W 851860476 960355168 W
output:
1 2
result:
ok
Test #2:
score: 6
Accepted
time: 4ms
memory: 61240kb
input:
2 714148610 688520844 W 359519570 789553998 S
output:
result:
ok
Test #3:
score: 6
Accepted
time: 7ms
memory: 59884kb
input:
2 743286406 87591094 E 108453484 326740470 S
output:
1 2
result:
ok
Test #4:
score: 6
Accepted
time: 4ms
memory: 60364kb
input:
2 629499666 659260200 W 391550936 897208930 N
output:
result:
ok
Test #5:
score: 6
Accepted
time: 7ms
memory: 59960kb
input:
2 509095668 374922996 W 325521434 191348762 S
output:
result:
ok
Test #6:
score: 6
Accepted
time: 7ms
memory: 59992kb
input:
2 357656592 713571312 E 456601638 614626266 S
output:
result:
ok
Test #7:
score: 6
Accepted
time: 15ms
memory: 60292kb
input:
2 353512742 374956722 W 265604916 462864548 N
output:
result:
ok
Test #8:
score: 6
Accepted
time: 0ms
memory: 60080kb
input:
2 253519292 302668732 E 436627396 119560628 S
output:
result:
ok
Test #9:
score: 6
Accepted
time: 14ms
memory: 59872kb
input:
2 741954822 709863076 W 516385128 484293380 S
output:
1 2
result:
ok
Test #10:
score: 6
Accepted
time: 11ms
memory: 61284kb
input:
2 268851874 524109226 E 503673708 758931058 N
output:
1 2
result:
ok
Test #11:
score: 6
Accepted
time: 7ms
memory: 60068kb
input:
2 629380956 395789270 S 557401140 467769088 E
output:
1 2
result:
ok
Test #12:
score: 6
Accepted
time: 8ms
memory: 60652kb
input:
2 606361496 587557658 N 667076156 526843000 W
output:
1 2
result:
ok
Test #13:
score: 6
Accepted
time: 4ms
memory: 59888kb
input:
2 270428340 629167054 N 270428342 179345630 S
output:
1 2
result:
ok
Subtask #2:
score: 0
Wrong Answer
Test #14:
score: 0
Wrong Answer
time: 4ms
memory: 60912kb
input:
100 32 46 N 8 24 W 74 86 W 2 76 N 90 70 N 34 74 N 4 68 N 42 26 N 66 94 N 28 40 W 96 12 W 82 78 W 54 24 N 36 42 W 92 68 W 0 26 N 14 54 N 94 66 N 26 52 N 66 12 W 72 6 W 64 96 W 6 20 N 4 22 W 26 42 N 40 28 W 70 76 N 18 60 N 62 16 N 30 48 N 36 36 W 42 36 W 52 94 N 62 98 N 0 78 N 70 2 W 28 50 N 80 80 W 8...
output:
78
result:
FAIL Unexpected end of file - token expected (/var/uoj_data/9161/14.ans)
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Wrong Answer
Test #58:
score: 0
Wrong Answer
time: 1952ms
memory: 152392kb
input:
200000 526715640 430855204 E 731546662 226024182 S 254814720 702756124 E 227354364 730216480 S 764250602 193320242 S 150102088 807468756 E 204858572 752712272 S 635512190 322058654 E 403910248 553660596 S 257917918 4587926 S 949444340 8126504 S 907805098 49765746 S 553836306 403734538 S 40977864 617...
output:
3403 8275 9880 13199 15693 16901 18411 21715 22022 23854 24320 26195 27113 27245 33529 34527 36965 41269 42079 42690 43151 44843 45683 50036 50595 50977 54767 56198 56869 59075 62188 62993 64110 65233 65951 67793 68734 69131 71705 72315 74185 74190 74918 75013 76507 77589 79906 80187 82347 82390 877...
result:
FAIL Unexpected end of file - token expected (/var/uoj_data/9161/58.ans)
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%