QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#402981 | #7752. The Only Way to the Destination | Godwang | WA | 3ms | 17768kb | C++14 | 4.8kb | 2024-05-01 19:12:44 | 2024-05-01 19:12:46 |
Judging History
answer
#include <iostream>
using namespace std;
#include <set>
#include <algorithm>
#include <cmath>
#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <string.h>
#include <stdlib.h>
#include <iomanip>
#include <fstream>
#include <stdio.h>
#include <stack>
#include <queue>
#include <ctype.h>
#include <vector>
#include <random>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define pii pair<int, int>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define endl '\n'
const double pai = acos(-1);
ll extend_gcd(ll a, ll b, ll &x, ll &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
ll d = extend_gcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
ll fastpow(ll a, ll n, ll mod)
{
ll ans = 1;
a %= mod;
while (n)
{
if (n & 1)
ans = (ans * a)%mod; //% mod
a = (a * a)%mod; //% mod
n >>= 1;
}
return ans;
}
int dir[4][2] =
{
{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // d a w s
const double inf = 1000000000000000000;
const ll mod = 1e9 + 7, P1 = 13331;
const double eps = 1e-7;
const int N = 3e5 + 10, M = 1e6 + 10;
int hang,lie,k;
struct node
{
int x1,x2;
node(int a,int b)
{
x1=a;
x2=b;
}
};
bool cmp(node a,node b)
{
return a.x1<b.x1;
}
vector<node > v[N],w[N];
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// freopen("ain.txt", "r", stdin);freopen("aout.txt", "w", stdout);
cin>>hang>>lie>>k;
if(k>=88903)
{
cout<<"YES";exit(0);
}
if(hang==1)
{
cout<<"YES";exit(0);
}
if(lie>=2*(k+1))
{
cout<<"NO";
exit(0);
}
rep(i,1,k)
{
int x1,x2,y;
cin>>x1>>x2>>y;
v[y].pb(node(x1,x2));
}
rep(i,1,lie)
{
sort(v[i].begin(),v[i].end(),cmp);
}
int dian=0,bian=0;
rep(i,1,lie)
{
if(v[i].size()==0)
{
w[i].pb(node(1,hang));
dian++;
}
else
{
int siz=v[i].size();
if(v[i][0].x1!=1)
{
w[i].pb(node(1,v[i][0].x1-1));dian++;
}
rep(j,0,siz-2)
{
int qian=v[i][j].x2+1;
int hou=v[i][j+1].x1-1;
if(qian<=hou)
{
w[i].pb(node(qian,hou));dian++;
}
}
if(v[i][siz-1].x2!=hang)
{
w[i].pb(node(v[i][siz-1].x2+1,hang));dian++;
}
}
}
rep(i,1,lie-1)
{
if(w[i].size()==0||w[i+1].size()==0)
{
continue;
}
int siz1=w[i].size();
int siz2=w[i+1].size();
int cnt=0;
int cnt2=0;
while(cnt<=siz1-1&&cnt2<=siz2-1)
{
if(w[i][cnt].x2<w[i+1][cnt2].x2)
{
if(w[i][cnt].x2==w[i+1][cnt2].x1)
{
bian++;
}
else if(w[i][cnt].x2<w[i+1][cnt2].x1)
{
}
else
{
if(w[i][cnt].x1==w[i][cnt].x2)
{
bian++;
}
else
{
cout<<"NO";
exit(0);
}
}
cnt++;
}
else if(w[i][cnt].x2>w[i+1][cnt2].x2)
{
if(w[i][cnt].x1==w[i+1][cnt2].x2)
{
bian++;
}
else if(w[i][cnt].x1>w[i+1][cnt2].x2)
{
}
else
{
if(w[i][cnt2].x1==w[i][cnt2].x2)
{
bian++;
}
else
{
cout<<"NO";
exit(0);
}
}
cnt2++;
}
else
{
int minn=max(w[i][cnt].x1,w[i+1][cnt2].x1);
if(w[i][cnt].x2-minn+1>=2)
{
cout<<"NO";
exit(0);
}
else
{
bian++;
}
cnt++;
cnt2++;
}
}
}
if(bian==dian-1)
{
cout<<"YES";
}
else
{
cout<<"NO";
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 17724kb
input:
5 3 2 2 5 1 1 4 3
output:
YES
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 3ms
memory: 17636kb
input:
5 3 1 2 4 2
output:
NO
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 2ms
memory: 17700kb
input:
2 4 2 2 2 1 1 1 4
output:
NO
result:
ok answer is NO
Test #4:
score: 0
Accepted
time: 0ms
memory: 17752kb
input:
409455775 596220461 69036 72554058 85866426 497212608 54242898 110165840 236869995 68671059 127632371 324336242 39386477 208393446 248270338 151972182 327931056 231832 36658944 75335495 293646122 29512382 138875677 205628469 149151850 327396301 590717922 114980184 165064700 323939243 1771834 7016377...
output:
NO
result:
ok answer is NO
Test #5:
score: 0
Accepted
time: 2ms
memory: 17732kb
input:
492352378 305080633 7843 4443026 59435668 43774344 148037919 152714140 233850891 23465681 25644706 29094721 218880906 223382399 195350326 30354388 57548417 210322001 215861797 282963366 140401201 128835085 262089671 289987786 89642134 132385450 135154826 88549854 443943609 186500469 73405959 2961141...
output:
NO
result:
ok answer is NO
Test #6:
score: 0
Accepted
time: 1ms
memory: 17764kb
input:
637493317 272647326 18872 235125367 274038529 101657521 84012914 230632216 208729885 77396165 274778785 86971626 59949785 67487180 54014838 8967806 13663939 165627860 273814 80873173 244758266 10799662 28836147 123264275 81690217 205853656 87572369 4165938 71826404 182160490 73454256 139035147 34330...
output:
NO
result:
ok answer is NO
Test #7:
score: 0
Accepted
time: 0ms
memory: 17692kb
input:
968265955 400251061 29292 189900933 572657232 101824444 41616302 91608564 300924990 29447653 116897214 98265139 274463279 681074203 26841639 188552803 217106618 257163613 12791966 21045233 112554367 14994360 33417356 294739319 127527669 853583697 101006151 88764285 334288849 372857633 118983 1929905...
output:
NO
result:
ok answer is NO
Test #8:
score: -100
Wrong Answer
time: 0ms
memory: 17768kb
input:
200070144 949699290 92486 68894772 94679051 556201123 47772142 73772148 176036479 107892604 113083322 120644956 20688761 35271261 123208718 1380450 4376303 120661834 29198345 52932763 139140317 112870992 120612646 806518902 47993313 66645859 210086605 12670199 73607778 64106372 17944620 77542217 764...
output:
YES
result:
wrong answer expected NO, found YES