제출 #1085179

#제출 시각아이디문제언어결과실행 시간메모리
1085179yeediot팀들 (IOI15_teams)C++17
0 / 100
414 ms361092 KiB
#include<bits/stdc++.h> #include "teams.h" using namespace std; #define ll long long #define F first #define S second #define all(x) x.begin(),x.end() #define pii pair<int,int> #define pb push_back #define sz(x) (int)(x.size()) #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) #define vi vector<int> #define vp vector<pii> #define vvi vector<vi> #define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()) #define __lg(x) 63-__builtin_clzll(x) #define pow2(x) (1LL<<x) const int mxn = 5e5 + 5; int cnt, rt[mxn]; struct segtree{ struct nde{ int l, r; ll c; }seg[mxn << 5]; #define x seg[node] ll build(int l, int r){ int node = ++cnt; seg[node].c = 0; if(l == r){ return node; } int mm = l + r >> 1; x.l = build(l, mm), x.r = build(mm + 1, r); return node; } ll ins(int from, int l, int r, int p){ int node = ++cnt; seg[node] = seg[from]; if(l == r){ seg[node].c++; return node; } int mm = l + r >> 1; if(p <= mm){ x.l = ins(x.l, l, mm, p); } else{ x.r = ins(x.r, mm + 1, r, p); } x.c = seg[x.l].c + seg[x.r].c; return node; } ll kth(int v, int u, int l, int r, int k){ if(l == r){ return l; } int mm = l + r >> 1; ll cc = seg[seg[v].r].c - seg[seg[u].r].c; if(k > cc){ return kth(seg[v].l, seg[u].l, l, mm, k - cc); } else{ return kth(seg[v].r, seg[u].r, mm + 1, r, k); } } ll bs(int v, int u, int l, int r, int k){ if(l == r){ return seg[v].c - seg[u].c; } int mm = l + r >> 1; if(k > mm){ return bs(seg[v].r, seg[u].r, mm + 1, r, k); } else{ return bs(seg[v].l, seg[u].l, l, mm, k) + seg[seg[v].r].c - seg[seg[u].r].c; } } }tr; int n; void init(int N, int a[], int b[]){ n = N; rt[0] = tr.build(1, n); vector<pii>pt; for(int i = 0; i < n; i++){ pt.pb({a[i], b[i]}); } sort(all(pt)); int pos = 0; for(int i = 1; i <= n; i++){ rt[i] = rt[i - 1]; for(; pos < n and pt[pos].F == i; pos++){ tr.ins(rt[i], 1, n, pt[pos].S); } } } int can(int m, int K[]){ vector<array<ll, 3>>st; vector<ll>k; for(int i = 0; i < m; i++) k.pb(K[i]); st.pb({0LL, 0LL, 0LL}); sort(all(k)); for(auto i : k){ while(sz(st) and st.back()[1] < i){ st.pop_back(); } ll tot = (ll)st.back()[2] + tr.bs(rt[i], rt[st.back()[0]], 1, n, i) - i; if(tot < 0){ return false; } ll cur = tr.kth(rt[i], rt[st.back()[0]], 1, n, tot - st.back()[2]); while(sz(st) and cur > st.back()[1]){ st.pop_back(); cur = tr.kth(rt[i], rt[st.back()[0]], 1, n, tot - st.back()[2]); } st.pb({i, cur, tot}); } return true; }

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

teams.cpp: In member function 'long long int segtree::build(int, int)':
teams.cpp:33:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |         int mm = l + r >> 1;
      |                  ~~^~~
teams.cpp:34:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   34 |         x.l = build(l, mm), x.r = build(mm + 1, r);
      |               ~~~~~^~~~~~~
teams.cpp:34:40: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   34 |         x.l = build(l, mm), x.r = build(mm + 1, r);
      |                                   ~~~~~^~~~~~~~~~~
teams.cpp: In member function 'long long int segtree::ins(int, int, int, int)':
teams.cpp:44:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |         int mm = l + r >> 1;
      |                  ~~^~~
teams.cpp:46:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   46 |             x.l = ins(x.l, l, mm, p);
      |                   ~~~^~~~~~~~~~~~~~~
teams.cpp:49:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   49 |             x.r = ins(x.r, mm + 1, r, p);
      |                   ~~~^~~~~~~~~~~~~~~~~~~
teams.cpp: In member function 'long long int segtree::kth(int, int, int, int, int)':
teams.cpp:58:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |         int mm = l + r >> 1;
      |                  ~~^~~
teams.cpp:61:53: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   61 |             return kth(seg[v].l, seg[u].l, l, mm, k - cc);
      |                                                   ~~^~~~
teams.cpp: In member function 'long long int segtree::bs(int, int, int, int, int)':
teams.cpp:71:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |         int mm = l + r >> 1;
      |                  ~~^~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:83:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   83 |     rt[0] = tr.build(1, n);
      |             ~~~~~~~~^~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:107:74: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  107 |         ll tot = (ll)st.back()[2] + tr.bs(rt[i], rt[st.back()[0]], 1, n, i) - i;
      |                                                                          ^
teams.cpp:111:60: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  111 |         ll cur = tr.kth(rt[i], rt[st.back()[0]], 1, n, tot - st.back()[2]);
teams.cpp:114:61: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  114 |             cur = tr.kth(rt[i], rt[st.back()[0]], 1, n, tot - st.back()[2]);
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...