QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#404949 | #3007. Intersecting Rectangles | Lspeed# | WA | 82ms | 15592kb | C++14 | 2.5kb | 2024-05-05 02:25:34 | 2024-05-05 02:25:35 |
Judging History
answer
#include<bits/stdc++.h>
#define x first
#define y second
#define eb emplace_back
#define pb push_back
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define sz(x) (int)(x).size()
#define make_unique(x) sort(all(x)), (x).erase(unique(all(x)), (x).end())
using namespace std;
typedef long long i64;
//typedef __int128 i128;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<i64> vl;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<i64,i64> pll;
typedef tuple<int,int,int> iii;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
int readInt() { int a; scanf("%d",&a); return a; }
i64 readLong() { i64 a; scanf("%lld",&a); return a; }
char readChar() { char a; scanf(" %c",&a); return a; }
double readDouble() { double a; scanf(" %lf",&a); return a; }
void readString(char *s) { scanf(" %s",s); }
const int mod = 998244353;
int add(int a, int b) { return ((a+=b)>=mod) ? a-mod:a; }
int mul(int a, int b) { return a*1ll*b%mod; }
int pw(int a, int b) {
int ans = 1, res = a;
for(int i = 1; i <= b; i*=2, res=mul(res,res)) {
if(i&b) {
ans = mul(ans, res);
}
}
return ans;
}
struct A{
int x, y1, y2;
int in;
A(int x, int y1, int y2, int in): x(x), y1(y1), y2(y2), in(in) {
}
bool operator < (const A& o) const {
if(x != o.x) return x < o.x;
return in > o.in;
}
};
int main() {
int n = readInt();
bool ans = false;
vector<A> event;
FOR(i,1,n) {
int x1,y1,x2,y2;
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
event.eb(x1, y1, y2, 1);
event.eb(x2, y1, y2, 0);
}
set<int> sweep;
sort(all(event));
for(int i = 0; i < sz(event); ) {
int j;
for(j = i; j < sz(event); ++j) {
if(event[j].x != event[i].x) {
break;
}
if(event[j].in) {
if(sweep.count(event[j].y1) != 0) {
//printf("wtf %d %d %d\n",event[j].x,event[j].y1,event[j].y2);
return !printf("1\n");
}
if(sweep.count(event[j].y2) != 0) {
//printf("wtf %d %d %d\n",event[j].x,event[j].y1,event[j].y2);
return !printf("1\n");
}
set<int>::iterator it, it2;
it = sweep.insert(event[j].y1).x;
it2 = sweep.insert(event[j].y2).x;
it++;
if(it != it2) {
//printf("wtf %d %d %d\n",event[j].x,event[j].y1,event[j].y2);
return !printf("1\n");
}
} else {
sweep.erase(event[j].y1);
sweep.erase(event[j].y2);
}
}
i = j;
}
printf("0\n");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 46ms
memory: 7588kb
input:
100000 -1000000 -1000000 -990000 -990000 -989500 -999999 -979500 -989999 -979000 -999998 -969000 -989998 -968500 -999997 -958500 -989997 -958000 -999996 -948000 -989996 -947500 -999995 -937500 -989995 -937000 -999994 -927000 -989994 -926500 -999993 -916500 -989993 -916000 -999992 -906000 -989992 -90...
output:
0
result:
ok answer is 0
Test #2:
score: 0
Accepted
time: 1ms
memory: 3736kb
input:
1 -1000000000 -1000000000 1000000000 1000000000
output:
0
result:
ok answer is 0
Test #3:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
13 7516209 7550707 89875156 98173013 47476247 5897894 76370217 37077815 8554547 13903693 70271199 58517091 59377179 10691227 85248839 74526588 25381296 75287750 63190532 94490939 1744167 1968914 33149094 90583877 3729241 63828859 70195565 67888762 23931088 47849774 35764715 67174851 82068785 3054639...
output:
1
result:
ok answer is 1
Test #4:
score: 0
Accepted
time: 26ms
memory: 8424kb
input:
100000 -10000000 -10000000 -9999802 -9999804 -9999800 -9999800 -9999602 -9999604 -9999600 -9999600 -9999402 -9999404 -9999400 -9999400 -9999202 -9999204 -9999200 -9999200 -9999002 -9999004 -9999000 -9999000 -9998802 -9998804 -9998800 -9998800 -9998602 -9998604 -9998600 -9998600 -9998402 -9998404 -99...
output:
0
result:
ok answer is 0
Test #5:
score: 0
Accepted
time: 35ms
memory: 9168kb
input:
100000 3035800 3035800 3035998 3035996 -1397800 -1397800 -1397602 -1397604 9002800 9002800 9002998 9002996 -3410800 -3410800 -3410602 -3410604 2188200 2188200 2188398 2188396 -7752600 -7752600 -7752402 -7752404 819600 819600 819798 819796 -4035400 -4035400 -4035202 -4035204 658800 658800 658998 6589...
output:
1
result:
ok answer is 1
Test #6:
score: 0
Accepted
time: 82ms
memory: 15592kb
input:
100000 -500000000 -300000000 400000000 290000000 -499999000 -299999000 399999100 289999100 -499998000 -299998000 399998200 289998200 -499997000 -299997000 399997300 289997300 -499996000 -299996000 399996400 289996400 -499995000 -299995000 399995500 289995500 -499994000 -299994000 399994600 289994600...
output:
0
result:
ok answer is 0
Test #7:
score: 0
Accepted
time: 28ms
memory: 8108kb
input:
100000 -500000000 -300000000 400000000 290000000 -499999000 -299999000 400000010 290000020 -499998000 -299998000 400000020 290000040 -499997000 -299997000 400000030 290000060 -499996000 -299996000 400000040 290000080 -499995000 -299995000 400000050 290000100 -499994000 -299994000 400000060 290000120...
output:
1
result:
ok answer is 1
Test #8:
score: 0
Accepted
time: 1ms
memory: 3736kb
input:
15 0 0 1000 1000 70 70 875 875 2 2 995 995 6 6 980 980 20 20 930 950 40 40 890 910 200 200 700 700 360 390 680 680 430 400 650 600 490 495 520 505 -1000 -1000 -800 -800 -2000 -2000 -1700 -1800 -400 -400 -200 -250 -125 -140 -95 -95 -3 -3 -1 -1
output:
0
result:
ok answer is 0
Test #9:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
16 0 0 1000 1000 70 70 875 875 2 2 995 995 6 6 980 980 20 20 930 950 40 40 890 910 65 69 905 920 200 200 700 700 360 390 680 680 430 400 650 600 490 495 520 505 -1000 -1000 -800 -800 -2000 -2000 -1700 -1800 -400 -400 -200 -250 -125 -140 -95 -95 -3 -3 -1 -1
output:
1
result:
ok answer is 1
Test #10:
score: 0
Accepted
time: 21ms
memory: 7668kb
input:
99900 -5000000 3000000 -4999992 3000011 -4999985 2999985 -4999977 2999996 -4999970 2999970 -4999962 2999981 -4999955 2999955 -4999947 2999966 -4999940 2999940 -4999932 2999951 -4999925 2999925 -4999917 2999936 -4999910 2999910 -4999902 2999921 -4999895 2999895 -4999887 2999906 -4999880 2999880 -4999...
output:
0
result:
ok answer is 0
Test #11:
score: -100
Wrong Answer
time: 42ms
memory: 8376kb
input:
99901 -5000000 3000000 -4999992 3000011 -4999985 2999985 -4999977 2999996 -4999970 2999970 -4999962 2999981 -4999955 2999955 -4999947 2999966 -4999940 2999940 -4999932 2999951 -4999925 2999925 -4999917 2999936 -4999910 2999910 -4999902 2999921 -4999895 2999895 -4999887 2999906 -4999880 2999880 -4999...
output:
0
result:
wrong answer expected 1, found 0