제출 #1286510

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286510		trinm01	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	279 ms	26464 KiB

fortune_telling2

// #pragma GCC optimize("O3")
// #pragma GCC optimization("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define ll long long
#define FOR(i, l, r) for (int i = (l); i <= (r); i++)
#define FOD(i, r, l) for (int i = (r); i >= (l); i--)
// #define fi first
// #define se second
// #define pii pair<int, int>

const ll mod = 1e9 + 7;
const int MAXN = 2e5 + 5;
const ll oo = 1e18 + 7;  
const int base = 10;

struct pii{
	int fi, se, id;
};

int n, q;
pii a[MAXN], b[MAXN];
pii tv[MAXN];

int st[4*MAXN], st2[4*MAXN];
void update(int id, int l, int r, int i, int val){
	if(l>i || r<i){
		return;
	}
	if(l>=r){
		st[id]=val;
		st2[id]+=val;
		return;
	}
	int mid=(l+r)/2;
	update(id*2, l, mid, i, val);
	update(id*2+1, mid+1, r, i, val);
	st[id]=max(st[id*2], st[id*2+1]);
	st2[id]=st2[id*2]+st2[id*2+1];
}
int walk(int id, int l, int r, int x){
	if(l>=r){
		return l;
	}
	int mid=(l+r)/2;
	if(st[id*2+1]>=x){
		return walk(id*2+1, mid+1, r, x);
	}
	return walk(id*2, l, mid, x);
}
int get(int id, int l, int r, int i, int j){
	if(i>j) return 0;
	if(l>j || r<i){
		return 0;
	}
	if(l>=i && r<=j){
		return st2[id];
	}
	int mid=(l+r)/2;
	return get(id*2, l, mid, i, j)+get(id*2+1, mid+1, r, i, j);
}

bool cmp2(pii a, pii b){
	return a.se<b.se;
}
bool cmp1(pii a, pii b){
	return a.fi<b.fi;
}

int pos[MAXN];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    
    // freopen("test.txt", "r", stdin);
    // freopen("o2.out", "w", stdout);

    if(fopen(".inp", "r")){
        freopen(".inp", "r", stdin);
        freopen(".out", "w", stdout);
    }

    cin >> n >> q;
    FOR(i, 1, n){
    	cin >> a[i].fi >> a[i].se;
    	a[i].id=i;
    	b[i]=a[i];
    	if(b[i].fi>b[i].se){
    		swap(b[i].fi, b[i].se);
    	}
    }
    FOR(i, 1, q){
    	int x;
    	cin >> x;
    	tv[i]={x, i, 0};
    }
    
    sort(b+1, b+1+n, cmp2);
    sort(tv+1, tv+1+q, cmp1);
    int j=1;
    FOR(i, 1, n){
    	while(j<=q && tv[j].fi<b[i].se){
    		update(1, 0, q, tv[j].se, tv[j].fi);
    		j++;
    	}
    	pos[i]=walk(1, 0, q, b[i].fi);
    	// cout << b[i].fi << ' ' << b[i].se << ' ';
    	// cout << pos[i] << '\n';
    }
    
    int sum=0;
    reverse(b+1, b+1+n);
    reverse(pos+1, pos+1+n);
    reverse(tv+1, tv+1+q);
    memset(st2, 0, sizeof st2);
    
    // FOR(i, 1, n){
    	// cout << b[i].fi << ' ' << b[i].se << '\n';
    // }
    
    j=1;
    FOR(i, 1, n){
    	while(j<=q && tv[j].fi>=b[i].se){
    		update(1, 1, q, tv[j].se, 1);
    		j++;
    	}
    	int dm=get(1, 1, q, pos[i]+1, q);
    	// cout << dm << ' ';
    	if(pos[i]==0){
    		if(dm%2==0){
    			sum+=a[b[i].id].fi;
    		}
    		else{
    			sum+=a[b[i].id].se;
    		}
    	}
    	else{
    		if(dm%2==0){
    			sum+=b[i].se;
    		}
    		else{
    			sum+=b[i].fi;
    		}
    	}
    	// cout << sum << '\n';
    }
    cout << sum;
    
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:85:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         freopen(".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:86:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         freopen(".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65