AtCoder ABC 128E Roadwork

题目链接：https://atcoder.jp/contests/abc128/tasks/abc128_e

题目大意

　　在一条路上（这条路可以看做坐标轴 x 轴从 0 开始方向为正无穷方向的射线），有 N 个道路工程，每个道路工程用三元组$(S_i, T_i, X_i)$表示，意思是第 i 个道路工程在$S_i$时间点开始，在$T_i$时间点完全结束（持续时间区间不包括$T_i$），施工地点是在 x 轴上的$X_i$位置。在同一地点的施工工程，他们的时间不会重叠。现在有 Q 个人依次从原点以一米每秒的速度在$D_i$时间点出发，碰到正在施工的工程就停下不走了，问每个人最后停下来的位置，如果停不下来，输出-1。

分析

　　对于第 i 个工程$(S_i, T_i, X_i)$，它只对出发时间在$[S_i - X_i, T_i - X_i)$区间内的人会起到阻塞作用，所以对于每一个人，我们只需要找到能对他起到阻塞作用且施工位置最前的工程位置就行了。

　　对于每一个$D_i$，与他有关的工程是那些已经开始但还没结束的，为了挑选出所有这些工程的位置，可以构造一个三元组$event(t_i, x_i, d_i)$，定义如下：

$d_i \in \{0, 1\}$。
当$d_i = 0$时，$t_i = S_i - X_i$。
当$d_i = 1$时，$t_i = T_i - X_i$。
$x_i = X_i$。

　　然后专门用一个集合存放与当前$D_i$有关的$X_i$，把三元组按照$t_i$排个序，然后顺序遍历所有$t_i \leq D_i$的事件，如果$d_i = 0$，就把$x_i$加入集合，否则就从集合中删去。

　　然后集合中最小的位置就是当前人所停留的位置。

代码如下

 #include <bits/stdc++.h>

 using namespace std;

 #define INIT() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

 #define Rep(i,n) for (int i = 0; i < (n); ++i)

 #define For(i,s,t) for (int i = (s); i <= (t); ++i)

 #define rFor(i,t,s) for (int i = (t); i >= (s); --i)

 #define ForLL(i, s, t) for (LL i = LL(s); i <= LL(t); ++i)

 #define rForLL(i, t, s) for (LL i = LL(t); i >= LL(s); --i)

 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)

 #define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i)

 #define pr(x) cout << #x << " = " << x << "  "

 #define prln(x) cout << #x << " = " << x << endl

 #define LOWBIT(x) ((x)&(-x))

 #define ALL(x) x.begin(),x.end()

 #define INS(x) inserter(x,x.begin())

 #define ms0(a) memset(a,0,sizeof(a))

 #define msI(a) memset(a,inf,sizeof(a))

 #define msM(a) memset(a,-1,sizeof(a))

 #define MP make_pair

 #define PB push_back

 #define ft first

 #define sd second

 template<typename T1, typename T2>

 istream &operator>>(istream &in, pair<T1, T2> &p) {

     in >> p.first >> p.second;

     return in;

 }

 template<typename T>

 istream &operator>>(istream &in, vector<T> &v) {

     for (auto &x: v)

         in >> x;

     return in;

 }

 template<typename T1, typename T2>

 ostream &operator<<(ostream &out, const std::pair<T1, T2> &p) {

     out << "[" << p.first << ", " << p.second << "]" << "\n";

     return out;

 }

 inline int gc(){

     static const int BUF = 1e7;

     static char buf[BUF], *bg = buf + BUF, *ed = bg;

     if(bg == ed) fread(bg = buf, , BUF, stdin);

     return *bg++;

 } 

 inline int ri(){

     int x = , f = , c = gc();

     for(; c<||c>; f = c=='-'?-:f, c=gc());

     for(; c>&&c<; x = x* + c - , c=gc());

     return x*f;

 }

 typedef long long LL;

 typedef unsigned long long uLL;

 typedef pair< double, double > PDD;

 typedef pair< int, int > PII;

 typedef pair< string, int > PSI;

 typedef set< int > SI;

 typedef vector< int > VI;

 typedef vector< PII > VPII;

 typedef map< int, int > MII;

 typedef multimap< int, int > MMII;

 typedef unordered_map< int, int > uMII;

 typedef pair< LL, LL > PLL;

 typedef vector< LL > VL;

 typedef vector< VL > VVL;

 typedef priority_queue< int > PQIMax;

 typedef priority_queue< int, VI, greater< int > > PQIMin;

 const double EPS = 1e-;

 const LL inf = 0x7fffffff;

 const LL infLL = 0x7fffffffffffffffLL;

 const LL mod = 1e9 + ;

 const int maxN = 2e5 + ;

 const LL ONE = ;

 const LL evenBits = 0xaaaaaaaaaaaaaaaa;

 const LL oddBits = 0x5555555555555555;

 struct Tuple{

     int T, X, D;

     inline bool operator< (const Tuple &x) const{

         return T < x.T;

     }

 };

 int N, Q;

 Tuple event[maxN << ];

 int len;

 multiset< int > msi;

 int main(){

     //INIT();

     N = ri();

     Q = ri();

     For(i, , N) {

         int S, T, X;

         S = ri();

         T = ri();

         X = ri();

         event[++len].T = S - X;

         event[len].X = X;

         event[len].D = ;

         event[++len].T = T - X;

         event[len].X = X;

         event[len].D = ;

     }

     sort(event + , event + len + );

     int k = , D;

     For(i, , Q) {

         D = ri();

         //********************************************************************

         while(k <= len) {

             if(event[k].T <= D) {

                 if(event[k].D) msi.insert(event[k].X);

                 else msi.erase(msi.find(event[k].X));

                 ++k;

             }

             else break;

         }

         /*

         血的教训，一开始我写的不是while循环，而是for循环，貌似是没问题

         但是提交一直超时，原因是某些案例使得else分支一直没有执行到，于是时间复杂度就激增了

         贴上错误代码，引以为戒

         For(j, k, len) {

             if(event[j].T <= D) {

                 if(event[j].D) msi.insert(event[j].X);

                 else msi.erase(msi.find(event[j].X));

                 ++k;

             }

             else {

                 k = j;

                 break;

             }

         }

         */

         //********************************************************************

         int ans = -;

         if(msi.size()) ans = *msi.begin();

         printf("%d\n", ans);

     }

     return ;

 }

巴特西

AtCoder ABC 128E Roadwork

题目大意

分析

代码如下

最新文章

热门文章