QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#602196#7752. The Only Way to the Destinationqinglu09TL 0ms3692kbC++142.1kb2024-09-30 20:54:302024-09-30 20:54:31

Judging History

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

  • [2024-09-30 20:54:31]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3692kb
  • [2024-09-30 20:54:30]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
#define endl '\n'
#define debug(x) cout<<#x<<": "<<x<<endl
#define lowbit(x) (x&-x)
#define gcd __gcd
#define i128 __int128
#define rep(i, a, b) for(ll i = (a); i <= (b); i++)
#define per(i, a, b) for(ll i = (a); i >= (b); i--)
const int N=2e5+10,M=1e3+10;
const ll mod=1e9+7;
const ld eps=1e-12;
const double pi=acos(-1.0);
const double pi1=pi/180,pi2=180/pi;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
//unordered_map<int,int>mp;
#define poly vector<int>

void solve()
{
    ll n,m,k;
    cin>>n>>m>>k;
    ll num_v=n*m;
    ll num_e=(m-1)*n+(n-1)*m;
    map<ll,vector<PLL>>path;
    while(k--)
    {
        ll x1,x2,y;
        cin>>x1>>x2>>y;
        path[y].push_back({x1,x2});
    }
    ll last_y=0;
    vector<PLL>last_q;
    last_q.push_back({1,n});
    for(auto [y,q]:path)
    {
        ll last_ed=0;
        sort(q.begin(),q.end());
        for(auto [st,ed]:q)
        {
            num_v-=ed-st+1;
            num_e-=ed-st+1;
            num_e-=ed-st;
            if(y!=m) num_e-=ed-st+1; 
            if(last_ed!=st-1) num_e--;
            if(ed!=n) num_e--;
            last_ed=ed;
        }
        if(y==last_y+1)
        {
            ll len1=last_q.size(),len2=q.size();
            ll p1=0,p2=0;
            while(p1<len1&&p2<len1)
            {
                auto [st1,ed1]=last_q[p1];
                auto [st2,ed2]=q[p2];
                ll l=max(st1,st2),r=min(ed1,ed2);
                num_e+=max(0ll,r-l+1);
                if(ed1<=ed2) p1++;
                else p2++;
            }
        }
        last_y=y;
        last_q=q;
    }
    if(num_e!=num_v&&num_e!=num_v-1) while(1);
    if(num_e==num_v-1) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	int T=1;
	//cin>>T;

	while(T--)
	{
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3680kb

input:

5 3 2
2 5 1
1 4 3

output:

YES

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

5 3 1
2 4 2

output:

NO

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

2 4 2
2 2 1
1 1 4

output:

NO

result:

ok answer is NO

Test #4:

score: -100
Time Limit Exceeded

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:


result: