QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#402981#7752. The Only Way to the DestinationGodwangWA 3ms17768kbC++144.8kb2024-05-01 19:12:442024-05-01 19:12:46

Judging History

你现在查看的是最新测评结果

  • [2024-05-01 19:12:46]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:17768kb
  • [2024-05-01 19:12:44]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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