Submission #59138213

Source Code Expand

#include <bits/stdc++.h>
#include<atcoder/all>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using namespace atcoder;
#define all(a) a.begin(),a.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef modint1000000007 mi;
constexpr ll mod=1000000007;

int l[300005],r[300005];

int main(){
	ll n,m;cin>>n>>m;
	ll ans=m*(m-1)/2;
	vector<P>V;
	rep(i,m){
		cin>>l[i]>>r[i];
		l[i]--;r[i]--;
		V.push_back({r[i],-l[i]});
	}

	sort(all(V));
	rep(i,m){
		l[i]=-V[i].second;
		r[i]=V[i].first;
	}
	fenwick_tree<ll>f(n+1),r2(n+1);

	rep(i,m){
		ans-=f.sum(l[i],r[i]);
		ans-=r2.sum(0,l[i]+1);
		f.add(l[i],1);
		r2.add(r[i],1);
	}

	cout<<ans<<endl;
}

Submission Info

Submission Time
Task 017 - Crossing Segments（★7）
User Rho17
Language C++ 20 (gcc 12.2)
Score 7
Code Size 697 Byte
Status AC
Exec Time 153 ms
Memory 14900 KiB

Judge Result

Set Name Sample Subtask1 Subtask2 All
Score / Max Score 0 / 0 1 / 1 2 / 2 4 / 4
Status
AC × 5
AC × 12
AC × 18
AC × 25
Set Name Test Cases
Sample sample01.txt, sample02.txt, sample03.txt, sample04.txt, sample05.txt
Subtask1 sample01.txt, sample02.txt, sample03.txt, sample04.txt, sample05.txt, subtask1_handmade.txt, subtask1_max00.txt, subtask1_max01.txt, subtask1_max02.txt, subtask1_random00.txt, subtask1_random01.txt, subtask1_random02.txt
Subtask2 sample01.txt, sample02.txt, sample03.txt, sample04.txt, sample05.txt, subtask1_handmade.txt, subtask1_max00.txt, subtask1_max01.txt, subtask1_max02.txt, subtask1_random00.txt, subtask1_random01.txt, subtask1_random02.txt, subtask2_max00.txt, subtask2_max01.txt, subtask2_max02.txt, subtask2_random00.txt, subtask2_random01.txt, subtask2_random02.txt
All sample01.txt, sample02.txt, sample03.txt, sample04.txt, sample05.txt, subtask1_handmade.txt, subtask1_max00.txt, subtask1_max01.txt, subtask1_max02.txt, subtask1_random00.txt, subtask1_random01.txt, subtask1_random02.txt, subtask2_max00.txt, subtask2_max01.txt, subtask2_max02.txt, subtask2_random00.txt, subtask2_random01.txt, subtask2_random02.txt, subtask3_handmade.txt, subtask3_max00.txt, subtask3_max01.txt, subtask3_max02.txt, subtask3_random00.txt, subtask3_random01.txt, subtask3_random02.txt
Case Name Status Exec Time Memory
sample01.txt AC 10 ms 3460 KiB
sample02.txt AC 1 ms 3724 KiB
sample03.txt AC 1 ms 3716 KiB
sample04.txt AC 1 ms 3572 KiB
sample05.txt AC 1 ms 3588 KiB
subtask1_handmade.txt AC 1 ms 3576 KiB
subtask1_max00.txt AC 1 ms 3568 KiB
subtask1_max01.txt AC 1 ms 3764 KiB
subtask1_max02.txt AC 1 ms 3760 KiB
subtask1_random00.txt AC 1 ms 3556 KiB
subtask1_random01.txt AC 1 ms 3544 KiB
subtask1_random02.txt AC 1 ms 3544 KiB
subtask2_max00.txt AC 37 ms 5800 KiB
subtask2_max01.txt AC 37 ms 5732 KiB
subtask2_max02.txt AC 38 ms 5828 KiB
subtask2_random00.txt AC 2 ms 3588 KiB
subtask2_random01.txt AC 22 ms 4704 KiB
subtask2_random02.txt AC 26 ms 5732 KiB
subtask3_handmade.txt AC 143 ms 14880 KiB
subtask3_max00.txt AC 150 ms 14900 KiB
subtask3_max01.txt AC 151 ms 14828 KiB
subtask3_max02.txt AC 153 ms 14864 KiB
subtask3_random00.txt AC 99 ms 11196 KiB
subtask3_random01.txt AC 100 ms 11272 KiB
subtask3_random02.txt AC 6 ms 4220 KiB