记录编号	419952	评测结果	AAAAAAAAAA
题目名称	罗伊德的防晒霜	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.649 s
提交时间	2017-07-03 17:28:18	内存使用	4.38 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MOD = 19283746;
const int MAXN = 1e6 + 10;

inline char getc(void){ 
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}

inline int in(void){ 
    register int res = 0, f = 1;
    register char tmp = getc();
    while(!isdigit(tmp) && tmp ^ '-') tmp = getc();
    if(tmp == '-') f = -1, tmp = getc();
    while(isdigit(tmp))
        res = (res + (res << 2) << 1) + (tmp ^ 48),
        tmp = getc();
    return res * f;
}

struct DATA{ 
    int a, b;

    DATA(){ ;}
    DATA(int _b, int _a){ 
        a = _a, b = _b;
    }

    bool operator < (const DATA &c) const { 
        return a < c.a;
    }
};

void Merge_sort(int l, int r);

int ans = 0, N;
vector<DATA> data;

int main(){ 
#ifndef LOCAL
    freopen("EOADtulad.in", "r", stdin);
    freopen("EOADtulad.out", "w", stdout);
#endif
    N = in();
    for(int i = 1; i <= N; ++i) { 
        data.push_back(DATA(in(), in()));
    }

    sort(data.begin(), data.end());
    Merge_sort(0, N - 1);

    printf("%d\n", ans);
    return 0;
}

void Merge_sort(int l, int r){ 
    static int tmp[MAXN];
    if(l == r) return ;
    register int mid = (l + r) >> 1;
    Merge_sort(l, mid);
    Merge_sort(mid + 1, r);

    int i = l, j = mid + 1, *k = tmp;
    while(i <= mid && j <= r) { 
        if(data[i].b > data[j].b){ 
            *(k++) = data[j++].b;
            (ans += mid - i + 1) %= MOD;
        } else *(k++) = data[i++].b;
    }

    while(i <= mid) *(k++) = data[i++].b;
    while(j <= r) *(k++) = data[j++].b;

    k = tmp;
    for(int p = l; p <= r; ++p) data[p].b = *(k++);

    return ;
}