Submission #668659

#TimeUsernameProblemLanguageResultExecution timeMemory
668659nolimiyaFortune Telling 2 (JOI14_fortune_telling2)C++14
35 / 100
3010 ms7372 KiB
#include <bits/stdc++.h> #include <math.h> //in the name of god,aka allah //**gray sety orz** #pragma comment(linker, "/stack:200000000") #pragma GCC optimize("Ofast") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-fhoist-adjacent-loads") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-fdelete-null-pointer-checks") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") #pragma GCC optimize("unroll-loops") using namespace std; #define pi pair<int , int> #define pii pair<long long , pair<long long , long long>> const int maxm = 2e5 + 5; const long long mod = 1e9 + 7 ; typedef long long ll; ll l,r,mid; ll n,m; bool isval(int mid){ //cout << mid <<" " << mid*mid-mid <<endl; if (((mid-1)*mid)/2 < m) return 0; return 1; } ll darage[maxm] , ss , mm; queue<int> q; bool vis[maxm] , gos[maxm]; pi pedaret[maxm*2]; int rp[maxm*2]; pi w[maxm]; ll dp[maxm]; //ll rw[maxm][maxm]; bool cmp(pi x , pi y){ return max(x.first,x.second)>max(y.first,y.second); } void build(ll v=1 , ll l=1 , ll r=m+1){ if(r-l==1){ rp[v] = 0, pedaret[v]={darage[l],l}; return; } ll mid = (l+r)/2; build(v*2,l,mid) , build(v*2+1,mid,r); rp[v]=rp[v*2]+rp[v*2+1]; pedaret[v]=max(pedaret[v*2],pedaret[v*2+1]); } void shift(ll id , ll v=1 , ll l=1 , ll r=m+1){ if(r-l==1){ rp[v] = 1 , pedaret[v] = {-1 , l}; return; } ll mid=(l+r)/2; if(id<mid) shift(id , v*2 , l , mid); else shift(id , v*2+1 , mid , r); rp[v] = rp[v*2] + rp[v*2+1]; pedaret[v] = max(pedaret[v*2] , pedaret[v*2+1]); } ll upd(ll x , ll v=1 , ll l=1 , ll r=m+1){ if(r-l<=1) return l; ll mid = (l+r)/2; if(pedaret[v*2+1].first>=x) return upd(x,v*2+1,mid,r); else return upd(x,v*2,l,mid); } ll get(int lx , int rx , int v=1 , int l=1 , int r=m+1){ if(r<=lx||rx<=l) return 0; if(lx<=l&&r<=rx) return rp[v]; ll mid = (l+r)/2; return get(lx,rx,v*2,l,mid)+get(lx,rx,v*2+1,mid,r); } map<ll,ll> mp; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin >>n>>m; for (int i=1; i<=n; i++) cin>>w[i].first>>w[i].second; sort(w+1,w+n+1,cmp); for (int i=1; i<=m; i++) cin>>darage[i]; build(); //cout<<55; for (int i=1; i<=n; i++){ mm = 0; if (w[i].second>w[i].first) swap(w[i].first,w[i].second) , mm = 1; while (pedaret[1].first>=w[i].first) shift(pedaret[1].second); //cout<<<69; if (pedaret[1].first>=w[i].second){//cout<<44<<endl; //cout<<get(upd(w[i].second),m+1)<<endl; if (get(upd(w[i].second),m+1)%2) ss+=w[i].second; else ss+=w[i].first; } //cout<<73; else{ ss+=((mm)?((rp[1]%2)?w[i].first:w[i].second):(((rp[1]%2)?w[i].second:w[i].first))); } //cout<<i<<endl; } cout<<ss; }

Compilation message (stderr)

fortune_telling2.cpp:5: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    5 | #pragma comment(linker, "/stack:200000000")
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...