이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define pii pair < int, int >
using namespace std;
const int N = 5e5+10, K = 5e5+10;
const int logN = 20, maxN = (1<<20), startpos = maxN-1;
int n, k, m;
pii ribe[N];
int najvecidrag[K];
int draginterval[K];
int cur;
int lowout[K];
int st[maxN<<1];
vector < int > dragulji;
int sol;
bool rip[K];
bool ripp[30][30];
int temp[30];
bool dragsort1( int a, int b ) {
if(najvecidrag[a] > najvecidrag[b]) return 1;
return 0;
}
bool dragsort2( int a, int b ) {
if(lowout[a] > lowout[b]) return 1;
return 0;
}
int add( int a, int b ) {
return (a + b >= m) ? a+b-m : a+b;
}
int mul( int a, int b ) {
return (ll) a * b % m;
}
inline void merge( int i ) {
st[i] = mul(st[i*2+1], st[i*2+2]);
return;
}
inline void update( int i, int v ) {
i += startpos;
st[i] += v;
while(i != 0) {
i = (i - 1) / 2;
merge(i);
}
return;
}
int main( void ) {
FIO
cin >> n >> k >> m;
for(int i = 0; i < n; i++) {
cin >> ribe[i].F >> ribe[i].S;
ribe[i].S--;
}
sort(ribe, ribe + n);
cur = 0;
for(int i = 0; i < n; i++) {
najvecidrag[ribe[i].S] = i;
while(ribe[cur].F * 2 <= ribe[i].F) {
cur++;
}
draginterval[ribe[i].S] = cur;
lowout[ribe[i].S] = n;
}
for(int i = 0; i < n; i++) {
if(i >= draginterval[ribe[i].S]) {
lowout[ribe[i].S] = min(lowout[ribe[i].S], i);
}
}
for(int i = 0; i < maxN<<1; i++) st[i] = 1;
for(int i = 0; i < n; i++) {
update(ribe[i].S, 1);
}
for(int i = 0; i < k; i++) {
dragulji.pb(i);
}
sort(dragulji.begin(), dragulji.end(), dragsort1);
cur = n-1;
for(int i = 0; i < k; i++) {
while(cur >= 0 && draginterval[dragulji[i]] <= cur) {
if(!rip[ribe[cur].S])update(ribe[cur].S, -1);
cur--;
}
// cout << st[startpos+0] << " " << st[startpos+1] << " " << st[startpos+2] << " " << st[startpos+3] << "\n";
update(dragulji[i], -1);
sol = add(sol, st[0]);
update(dragulji[i], 1-st[dragulji[i] + startpos]);
rip[dragulji[i]] = 1;
// cout << st[startpos+0] << " " << st[startpos+1] << " " << st[startpos+2] << " " << st[startpos+3] << "\n\n";
}
for(int i = 0; i < k; i++) rip[i] = 0;
// cout << sol << "\n";
cur = n-1;
for(int i = 0; i < maxN<<1; i++) st[i] = 1;
for(int i = 0; i < n; i++) {
update(ribe[i].S, 1);
}
for(int i = 0; i < k; i++) {
for(int j = 0; j < k; j++) {
if(draginterval[i] > lowout[j]) {
ripp[j][i] = 1;
}
if(i==j) ripp[j][i] = 1;
}
}
// cout << st[startpos+0] << " " << st[startpos+1] << " " << st[startpos+2] << "\n\n\n";
for(int i = 0; i < k; i++) {
while(cur >= 0 && draginterval[dragulji[i]] <= cur) {
update(ribe[cur].S, -1);
cur--;
}
// cout << st[startpos+0] << " " << st[startpos+1] << " " << st[startpos+2] << "\n";
for(int j = 0; j < k; j++) {
if(ripp[dragulji[i]][j]) {
temp[j] = st[j + startpos] - 1;
update(j, - temp[j]);
}
}
sol = add(sol, st[0]);
// cout << st[startpos+0] << " " << st[startpos+1] << " " << st[startpos+2] << "\n\n";
for(int j = 0; j < k; j++) {
if(ripp[dragulji[i]][j]) {
update(j, temp[j]);
}
}
}
cout << sol;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |