Submission #554727

#TimeUsernameProblemLanguageResultExecution timeMemory
554727cheetoseFortune Telling 2 (JOI14_fortune_telling2)C++17
100 / 100
453 ms63744 KiB
#include <bits/stdc++.h> #define mp make_pair #define pb push_back #define X first #define Y second #define y0 y12 #define y1 y22 #define INF 987654321987654321 #define PI 3.141592653589793238462643383279502884 #define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c)) #define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c)) #define MEM0(a) memset((a),0,sizeof(a)) #define MEM_1(a) memset((a),-1,sizeof(a)) #define ALL(a) a.begin(),a.end() #define COMPRESS(a) sort(ALL(a));a.resize(unique(ALL(a))-a.begin()) #define SYNC ios_base::sync_with_stdio(false);cin.tie(0) using namespace std; typedef long long ll; typedef long double ld; typedef double db; typedef unsigned int uint; typedef unsigned long long ull; typedef pair<int, int> Pi; typedef pair<ll, ll> Pll; typedef pair<ld, ld> Pd; typedef vector<int> Vi; typedef vector<ll> Vll; typedef vector<ld> Vd; typedef vector<Pi> VPi; typedef vector<Pll> VPll; typedef vector<Pd> VPd; typedef tuple<int, int, int> iii; typedef tuple<int, int, int, int> iiii; typedef tuple<ll, ll, ll> LLL; typedef vector<iii> Viii; typedef vector<LLL> VLLL; typedef complex<double> base; const int MOD = 998244353; ll POW(ll a, ll b, ll MMM = MOD) { ll ret = 1; for (; b; b >>= 1, a = (a*a) % MMM)if (b & 1)ret = (ret*a) % MMM; return ret; } int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 }; int ddx[] = { -1,-2,1,-2,2,-1,2,1 }, ddy[] = { -2,-1,-2,1,-1,2,1,2 }; int a[200000],b[200000],t[200000],rev[200000]; Vi v[600000],q[600000]; int tree[1<<21]; int mx[600000]; void init(int node,int S,int E){ if(S==E){ tree[node]=mx[S]; return; } int L=node<<1,R=L|1,M=S+E>>1; init(L,S,M); init(R,M+1,E); tree[node]=max(tree[L],tree[R]); } int find(int node,int S,int E,int i,int j){ if(i>E || j<S)return -1; if(i<=S && j>=E)return tree[node]; int L=node<<1,R=L|1,M=S+E>>1; return max(find(L,S,M,i,j),find(R,M+1,E,i,j)); } int T[200005]; int n,m; void upd(int i,int k){ i++; while(i<=m){ T[i]+=k; i+=(i&-i); } } int sum(int i){ i++; int c=0; while(i>0){ c+=T[i]; i-=(i&-i); } return c; } int sum(int i,int j){ return sum(j)-sum(i-1); } int main(){ MEM_1(mx); Vi vv; scanf("%d%d",&n,&m); fup(i,0,n-1,1){ scanf("%d%d",a+i,b+i); vv.pb(a[i]);vv.pb(b[i]); if(a[i]>b[i])swap(a[i],b[i]); else rev[i]=1; } fup(i,0,m-1,1){ scanf("%d",t+i); vv.pb(t[i]); } COMPRESS(vv); int N=vv.size(); fup(i,0,n-1,1){ a[i]=lower_bound(ALL(vv),a[i])-vv.begin(),b[i]=lower_bound(ALL(vv),b[i])-vv.begin(); q[b[i]].pb(i); } fup(i,0,m-1,1){ t[i]=lower_bound(ALL(vv),t[i])-vv.begin(); v[t[i]].pb(i); mx[t[i]]=i; } init(1,0,N-1); ll ans=0; fdn(k,N-1,0,1){ for(int x:v[k])upd(x,1); for(int i:q[k]){ int r=find(1,0,N-1,a[i],b[i]-1); int d; if(r==-1)d=sum(0,m-1)+rev[i]; else d=sum(r+1,m-1); if(d&1)ans+=vv[a[i]]; else ans+=vv[b[i]]; } } printf("%lld\n",ans); }

Compilation message (stderr)

fortune_telling2.cpp: In function 'void init(int, int, int)':
fortune_telling2.cpp:52:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |  int L=node<<1,R=L|1,M=S+E>>1;
      |                        ~^~
fortune_telling2.cpp: In function 'int find(int, int, int, int, int)':
fortune_telling2.cpp:60:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |  int L=node<<1,R=L|1,M=S+E>>1;
      |                        ~^~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:10:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
      |                              ^
fortune_telling2.cpp:89:2: note: in expansion of macro 'fup'
   89 |  fup(i,0,n-1,1){
      |  ^~~
fortune_telling2.cpp:10:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
      |                              ^
fortune_telling2.cpp:95:2: note: in expansion of macro 'fup'
   95 |  fup(i,0,m-1,1){
      |  ^~~
fortune_telling2.cpp:10:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
      |                              ^
fortune_telling2.cpp:101:2: note: in expansion of macro 'fup'
  101 |  fup(i,0,n-1,1){
      |  ^~~
fortune_telling2.cpp:10:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
      |                              ^
fortune_telling2.cpp:105:2: note: in expansion of macro 'fup'
  105 |  fup(i,0,m-1,1){
      |  ^~~
fortune_telling2.cpp:11:30: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
   11 | #define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c))
      |                              ^
fortune_telling2.cpp:112:2: note: in expansion of macro 'fdn'
  112 |  fdn(k,N-1,0,1){
      |  ^~~
fortune_telling2.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
fortune_telling2.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |   scanf("%d%d",a+i,b+i);
      |   ~~~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |   scanf("%d",t+i);
      |   ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...