QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#402422 | #8540. Splitting Haybales | PatrickStar | 0 | 179ms | 55288kb | C++14 | 1.5kb | 2024-04-30 15:41:09 | 2024-04-30 15:41:10 |
Judging History
answer
//
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 1e6, mod = 1e9+7;
int n;
struct e{
int l, r;
}a[MAXN+5];
bool cmp(e x, e y) {
return x.l<y.l;
}
struct w{
int id, u;
};
bool operator <(w x, w y) {
return x.u<y.u;
}
multiset<w> s, rub;
vector<int> v[MAXN+5];
void connect(int x, int y) {
v[x].push_back(y);
v[y].push_back(x);
return ;
}
bool vis[MAXN+5], col[MAXN+5], flag;
void dfs(int i) {
vis[i] = 1;
for (int p=0;p<v[i].size();p++) {
if (!vis[v[i][p]]) {
col[v[i][p]] = !col[i];
dfs(v[i][p]);
if (flag) return ;
}
else if (col[i]==col[v[i][p]]) {
flag = 1;
return ;
}
}
return ;
}
int main() {
scanf("%d", &n);
for (int p=1;p<=n;p++) {
scanf("%d %d", &a[p].l, &a[p].r);
}
stable_sort(a+1, a+n+1, cmp);
int MAX = 0;
for (int p=1;p<=n;p++) {
if (a[p].r>MAX) {
MAX = a[p].r;
auto i = s.lower_bound({0, a[p].l}), j = s.upper_bound({0, a[p].r});
vector<w> temp;
while (i!=j) {
w t = *i;
connect(p, t.id);
temp.push_back(t);
i++;
}
for (int k=0;k+1<temp.size();k++) {
s.erase(s.find(temp[k]));
}
}
else {
auto i = rub.lower_bound({0, a[p].l});
if ((*i).u<=a[p].r) connect(p, (*i).id);
}
s.insert({p, a[p].r});
rub.insert({p, a[p].r});
}
ll ans = 1;
for (int p=1;p<=n;p++) {
if (!vis[p]) {
ans = ans*2%mod;
dfs(p);
if (flag) {
cout<<0;
return 0;
}
}
}
cout<<ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 28264kb
input:
2 3 1 15 1 1 -2 1 1 -1 1 1 0 1 1 1 1 1 2 1 2 -2 1 2 -1 1 2 0 1 2 1 1 2 2 2 2 -2 2 2 -1 2 2 0 2 2 1 2 2 2
output:
2
result:
wrong answer 1st lines differ - expected: '1', found: '2'
Test #2:
score: 0
Wrong Answer
time: 0ms
memory: 30588kb
input:
5 4 4 3 1 1 7 1 1 20 1 2 20 1 5 20 1 1 0 1 5 0 1 4 0 3 5 2
output:
16
result:
wrong answer 2nd lines differ - expected: '12', found: ''
Test #3:
score: 0
Wrong Answer
time: 90ms
memory: 52788kb
input:
200000 199998 199997 199996 199995 199994 199994 199993 199992 199992 199991 199991 199990 199990 199988 199987 199986 199986 199985 199984 199983 199982 199980 199979 199979 199976 199976 199975 199974 199974 199974 199974 199972 199971 199970 199970 199970 199969 199968 199968 199967 199967 199967...
output:
0
result:
wrong answer 1st lines differ - expected: '-42604', found: '0'
Test #4:
score: 0
Wrong Answer
time: 154ms
memory: 53068kb
input:
200000 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169 199169...
output:
0
result:
wrong answer 1st lines differ - expected: '23636', found: '0'
Test #5:
score: 0
Wrong Answer
time: 136ms
memory: 55288kb
input:
200000 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702 196702...
output:
0
result:
wrong answer 1st lines differ - expected: '57359', found: '0'
Test #6:
score: 0
Wrong Answer
time: 179ms
memory: 49044kb
input:
200000 200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
0
result:
wrong answer 1st lines differ - expected: '80942', found: '0'
Test #7:
score: 0
Wrong Answer
time: 163ms
memory: 52100kb
input:
200000 200000 199999 199991 199988 199980 199971 199967 199959 199946 199936 199934 199934 199926 199924 199921 199910 199909 199905 199892 199892 199892 199888 199883 199882 199878 199877 199873 199872 199863 199859 199857 199855 199854 199853 199847 199844 199842 199838 199837 199833 199829 199828...
output:
0
result:
wrong answer 2nd lines differ - expected: '683077295', found: ''
Test #8:
score: 0
Wrong Answer
time: 162ms
memory: 52124kb
input:
200000 199988 199987 199985 199978 199976 199974 199962 199962 199960 199952 199950 199949 199946 199938 199931 199927 199920 199917 199914 199909 199907 199905 199901 199900 199897 199890 199885 199871 199850 199842 199840 199835 199835 199831 199829 199819 199818 199810 199809 199808 199807 199806...
output:
0
result:
wrong answer 1st lines differ - expected: '237395027', found: '0'
Test #9:
score: 0
Wrong Answer
time: 164ms
memory: 51080kb
input:
200000 199999 199999 199991 199990 199989 199986 199984 199983 199982 199981 199979 199977 199973 199973 199973 199972 199971 199969 199967 199964 199963 199962 199962 199961 199960 199959 199954 199953 199950 199950 199948 199947 199942 199938 199935 199934 199932 199931 199930 199925 199925 199922...
output:
0
result:
wrong answer 1st lines differ - expected: '-618058211', found: '0'
Test #10:
score: 0
Wrong Answer
time: 155ms
memory: 51332kb
input:
200000 200000 199996 199994 199993 199991 199990 199990 199989 199981 199980 199979 199977 199973 199971 199968 199967 199967 199964 199963 199960 199958 199958 199955 199947 199946 199945 199945 199945 199945 199943 199940 199940 199940 199938 199936 199935 199934 199932 199932 199930 199926 199925...
output:
0
result:
wrong answer 1st lines differ - expected: '-263580135', found: '0'
Test #11:
score: 0
Wrong Answer
time: 178ms
memory: 50968kb
input:
200000 199999 199999 199998 199998 199996 199996 199996 199993 199991 199991 199990 199990 199986 199985 199984 199984 199982 199981 199981 199976 199970 199968 199966 199965 199962 199960 199960 199957 199952 199951 199950 199945 199944 199942 199942 199941 199940 199938 199938 199935 199935 199934...
output:
0
result:
wrong answer 1st lines differ - expected: '937427738', found: '0'
Test #12:
score: 0
Wrong Answer
time: 164ms
memory: 51076kb
input:
200000 199999 199998 199998 199996 199994 199994 199993 199988 199986 199985 199983 199981 199981 199979 199977 199975 199973 199972 199972 199971 199970 199970 199967 199961 199961 199955 199952 199950 199947 199946 199943 199940 199938 199937 199933 199933 199933 199931 199928 199919 199915 199915...
output:
0
result:
wrong answer 1st lines differ - expected: '22101', found: '0'
Test #13:
score: 0
Wrong Answer
time: 171ms
memory: 49888kb
input:
200000 199999 199999 199998 199998 199996 199996 199993 199992 199992 199992 199990 199989 199989 199989 199989 199988 199988 199986 199985 199982 199982 199981 199979 199978 199978 199978 199977 199977 199976 199975 199975 199972 199972 199971 199970 199969 199969 199967 199964 199964 199963 199963...
output:
0
result:
wrong answer 2nd lines differ - expected: '1', found: ''
Test #14:
score: 0
Wrong Answer
time: 167ms
memory: 49484kb
input:
200000 199997 199993 199993 199993 199993 199992 199992 199991 199991 199990 199990 199990 199990 199986 199982 199982 199982 199980 199977 199977 199976 199974 199974 199974 199973 199973 199973 199971 199969 199968 199968 199966 199965 199965 199964 199963 199963 199962 199962 199962 199962 199961...
output:
0
result:
wrong answer 2nd lines differ - expected: '-55846', found: ''
Test #15:
score: 0
Wrong Answer
time: 166ms
memory: 49836kb
input:
200000 199996 199996 199995 199992 199991 199989 199988 199988 199986 199986 199985 199984 199983 199982 199982 199980 199978 199978 199973 199972 199971 199969 199969 199969 199969 199968 199968 199967 199967 199967 199967 199964 199961 199961 199960 199959 199959 199959 199958 199957 199956 199955...
output:
0
result:
wrong answer 1st lines differ - expected: '-59946', found: '0'
Test #16:
score: 0
Wrong Answer
time: 174ms
memory: 50464kb
input:
200000 200000 199998 199996 199995 199993 199989 199988 199986 199985 199985 199985 199984 199979 199978 199977 199976 199974 199970 199969 199968 199968 199968 199966 199965 199964 199963 199963 199963 199961 199961 199961 199959 199959 199958 199958 199957 199956 199956 199955 199954 199954 199952...
output:
0
result:
wrong answer 1st lines differ - expected: '20400', found: '0'
Test #17:
score: 0
Wrong Answer
time: 170ms
memory: 52184kb
input:
200000 200000 200000 200000 200000 200000 200000 199998 199998 199998 199998 199996 199996 199996 199996 199996 199996 199994 199994 199994 199994 199992 199992 199992 199992 199992 199992 199990 199990 199990 199990 199990 199990 199988 199988 199988 199988 199986 199986 199986 199986 199984 199984...
output:
0
result:
wrong answer 1st lines differ - expected: '25728', found: '0'
Test #18:
score: 0
Wrong Answer
time: 154ms
memory: 54296kb
input:
200000 200000 200000 200000 200000 199998 199998 199998 199998 199998 199998 199996 199996 199996 199996 199996 199996 199994 199994 199994 199994 199994 199994 199992 199992 199992 199992 199990 199990 199990 199990 199988 199988 199988 199988 199988 199988 199986 199986 199986 199986 199984 199984...
output:
0
result:
wrong answer 1st lines differ - expected: '-1', found: '0'
Test #19:
score: 0
Wrong Answer
time: 156ms
memory: 51048kb
input:
200000 199999 199998 199998 199997 199996 199996 199996 199996 199995 199995 199994 199994 199993 199990 199990 199989 199988 199986 199985 199985 199984 199984 199983 199980 199979 199979 199979 199979 199977 199977 199976 199976 199974 199973 199972 199971 199971 199970 199968 199966 199964 199960...
output:
0
result:
wrong answer 1st lines differ - expected: '13228', found: '0'
Test #20:
score: 0
Wrong Answer
time: 161ms
memory: 50212kb
input:
200000 199998 199995 199994 199993 199993 199992 199992 199991 199988 199986 199985 199985 199982 199981 199979 199978 199978 199977 199977 199977 199975 199975 199973 199971 199971 199970 199969 199968 199968 199967 199967 199963 199963 199962 199960 199959 199958 199958 199957 199956 199956 199954...
output:
0
result:
wrong answer 1st lines differ - expected: '4', found: '0'
Test #21:
score: 0
Wrong Answer
time: 168ms
memory: 49676kb
input:
200000 200000 199999 199999 199998 199996 199995 199994 199994 199993 199991 199990 199989 199988 199988 199985 199985 199981 199980 199980 199980 199980 199979 199979 199978 199975 199973 199972 199970 199969 199969 199969 199968 199968 199966 199965 199965 199963 199961 199961 199961 199958 199958...
output:
0
result:
wrong answer 1st lines differ - expected: '-20767', found: '0'
Test #22:
score: 0
Wrong Answer
time: 167ms
memory: 51560kb
input:
200000 200000 200000 199999 199997 199997 199996 199996 199995 199992 199991 199990 199989 199988 199988 199987 199987 199987 199986 199984 199984 199983 199982 199982 199982 199979 199979 199979 199974 199973 199972 199972 199970 199969 199969 199969 199967 199967 199965 199964 199961 199960 199956...
output:
0
result:
wrong answer 2nd lines differ - expected: '-116796', found: ''