提出 #18906388

---

ソースコード 拡げる

//Author: RingweEH
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define db double
using namespace std;
int min( int a,int b ) { return a<b ? a : b; }
int max( int a,int b ) { return a>b ? a : b; }
int read()
{
    int x=0,w=1; char ch=getchar();
    while ( ch>'9' || ch<'0' ) { if ( ch=='-' ) w=-1; ch=getchar(); }
    while ( ch<='9' && ch>='0' ) x=x*10+ch-'0',ch=getchar();
    return x*w;
}

#define lowbit(x) ((x)&(-x))
const int N=2e5+10;
int n,m,q,mfir[N];
pair<int,int> p[N*3];
bool vis[N];
struct BIT
{
	int tr[N];
	BIT() { memset( tr,0,sizeof(tr) ); }
	void add( int x ) { for ( ; x<=m; x+=lowbit(x) ) tr[x]+=1; }
	int sum( int x ) { int res=0; for ( ; x; x-=lowbit(x) ) res+=tr[x]; return res; }
}Tr;

int main()
{
    n=read(); m=read(); q=read();
    int limx=n+1,limy=m+1;
    for ( int i=1; i<=q; i++ )
    {
        int x=read(),y=read();
        p[i].first=x; p[i].second=y;
        if ( x==1 ) limy=min( limy,y );
        if ( y==1 ) limx=min( limx,x );
    }

    for ( int i=limx+1; i<=n; i++ )
        q++,p[q].first=i,p[q].second=1;
    for ( int i=limy+1; i<=m; i++ )
        q++,p[q].first=1,p[q].second=i;
    sort( p+1,p+1+q );
    q=unique( p+1,p+1+q )-p-1;
    int las=1; ll ans=0;
    for ( int i=1; i<=q; i++ )
    {
        if ( vis[p[i].second]==0 ) { vis[p[i].second]=1; Tr.add(p[i].second); }
        if ( i==q || p[i+1].first!=p[i].first )
        {
            ans+=Tr.sum(m)-Tr.sum(p[las].second-1); las=i+1;
        }
    }

    printf( "%lld\n",1ll*n*m-ans );
}

提出情報

ジャッジ結果